[PATCH 0/3] Fix some ASID range size calculation issues in global ASID allocation

[PATCH 0/3] Fix some ASID range size calculation issues in global ASID allocation

[Hou Wenlong]

During the code review of the global ASID allocation, I found some ASID
range size calculation issues and I'm not sure if I missread.

Firstly, as described in the comments, the range for global ASIDs is
[TLB_NR_DYN_SIZE,MAX_ASID_AVAILABLE-1], which is a close interval. So
the size of range is '(MAX_ASID_AVAILABLE-1)- TLB_NR_DYN_SIZE + 1'.
However, 'global_asid_available' is set as 'MAX_ASID_AVAILABLE -
TLB_NR_DYN_ASIDS - 1', which means one ASID is missed.

The macro 'MAX_ASID_AVAILABLE', as I understand it, is used to represent
the maximum valid ASID. Thus the available ASID range described in the
comments is [0,MAX_ASID_AVAILABLE], which is a close interval too. So
the acutal size of the range is 'MAX_ASID_AVAILABLE + 1'. But it is
incorrectly used as the size of the bitmap in global ASID allocation,
leading to the maximum ASID number being excluded from global ASID
allocation.

Hou Wenlong (3):
  x86/mm: Correct the actual count of available global ASIDs
  mm/tlb: Fix wrong judgement in allocate_global_asid()
  x86/mm: Fix wrong usage of 'MAX_ASID_AVAILABLE' in global ASID
    allocation

 arch/x86/mm/tlb.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

--
2.31.1

[PATCH 1/3] x86/mm: Correct the actual count of available global ASIDs

[Hou Wenlong]

The available ASID range for global ASID allocation is
[TLB_NR_DYN_ASIDS, MAX_ASID_AVAILABLE-1], which is a close interval. So
the actual count of available ASIDs for global ASID allocation should be
'(MAX_ASID_AVIALBE-1) - TLB_NR_DYN_ASIDS + 1'.

Fixes: d504d1247e36 ("x86/mm: Add global ASID allocation helper functions")
Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>
---
 arch/x86/mm/tlb.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/x86/mm/tlb.c b/arch/x86/mm/tlb.c
index e459d97ef397..cad4a8eae2d8 100644
--- a/arch/x86/mm/tlb.c
+++ b/arch/x86/mm/tlb.c
@@ -279,7 +279,7 @@ static DEFINE_RAW_SPINLOCK(global_asid_lock);
 static u16 last_global_asid = MAX_ASID_AVAILABLE;
 static DECLARE_BITMAP(global_asid_used, MAX_ASID_AVAILABLE);
 static DECLARE_BITMAP(global_asid_freed, MAX_ASID_AVAILABLE);
-static int global_asid_available = MAX_ASID_AVAILABLE - TLB_NR_DYN_ASIDS - 1;
+static int global_asid_available = MAX_ASID_AVAILABLE - TLB_NR_DYN_ASIDS;
 
 /*
  * When the search for a free ASID in the global ASID space reaches
-- 
2.31.1

Re: [PATCH 1/3] x86/mm: Correct the actual count of available global ASIDs

[Rik van Riel]

On Sat, 2025-03-29 at 21:05 +0800, Hou Wenlong wrote:
> 
> +++ b/arch/x86/mm/tlb.c
> @@ -279,7 +279,7 @@ static DEFINE_RAW_SPINLOCK(global_asid_lock);
>  static u16 last_global_asid = MAX_ASID_AVAILABLE;
>  static DECLARE_BITMAP(global_asid_used, MAX_ASID_AVAILABLE);
>  static DECLARE_BITMAP(global_asid_freed, MAX_ASID_AVAILABLE);
> -static int global_asid_available = MAX_ASID_AVAILABLE -
> TLB_NR_DYN_ASIDS - 1;
> +static int global_asid_available = MAX_ASID_AVAILABLE -
> TLB_NR_DYN_ASIDS;

Unfortunately we are limited by the PCID space.

A process with ASID N will get PCID N+1.

The PCID space has the same size (and maximum value)
as the ASID space.

That means we cannot use the top ASID value.

Alternatively, I suppose we could have ASID and PCID
line up, and always exclude ASID 0 from being used.

That might (maybe) be prettier code, but it isn't what
we have today.


-- 
All Rights Reversed.

Re: [PATCH 1/3] x86/mm: Correct the actual count of available global ASIDs

[Hou Wenlong]

On Sun, Mar 30, 2025 at 01:29:25AM +0800, Rik van Riel wrote:
> On Sat, 2025-03-29 at 21:05 +0800, Hou Wenlong wrote:
> > 
> > +++ b/arch/x86/mm/tlb.c
> > @@ -279,7 +279,7 @@ static DEFINE_RAW_SPINLOCK(global_asid_lock);
> >  static u16 last_global_asid = MAX_ASID_AVAILABLE;
> >  static DECLARE_BITMAP(global_asid_used, MAX_ASID_AVAILABLE);
> >  static DECLARE_BITMAP(global_asid_freed, MAX_ASID_AVAILABLE);
> > -static int global_asid_available = MAX_ASID_AVAILABLE -
> > TLB_NR_DYN_ASIDS - 1;
> > +static int global_asid_available = MAX_ASID_AVAILABLE -
> > TLB_NR_DYN_ASIDS;
> 
> Unfortunately we are limited by the PCID space.
> 
> A process with ASID N will get PCID N+1.
> 
> The PCID space has the same size (and maximum value)
> as the ASID space.
> 
> That means we cannot use the top ASID value.
>
Thank you for your quick reply!

Since the size of the bitmap is 'MAX_ASID_AVAILABLE', the maximum ASID
value that can be allocated from the bitmap is 'MAX_ASID_AVAILABLE-1'.
This matches the comments stating that the valid ASID range for global
ASID allocation is [TLB_NR_DYN_ASIDS, MAX_ASID_AVAILABLE-1]. It is a
close interval so the size should be '(MAX_ASID_AVAILABLE-1)-TLB_NR_DYN_ASIDS+1',
regardless of the value of 'MAX_ASID_AVAILABLE'. Moreover, 'MAX_ASID_AVAILABLE'
has already taken the reserved PCID 0 into account; 'MAX_ASID_AVAILABLE-1' is a
valid ASID, and the associated PCID 'MAX_ASID_AVAILABLE' is also a valid PCID.
Did I miss something?

> Alternatively, I suppose we could have ASID and PCID
> line up, and always exclude ASID 0 from being used.
> 
> That might (maybe) be prettier code, but it isn't what
> we have today.
>
Yes, I agree. Excluding ASID 0 and using PCID as ASID makes the code
clearer in global ASID allocation.

> 
> -- 
> All Rights Reversed.

[PATCH 2/3] mm/tlb: Fix wrong judgement in allocate_global_asid()

[Hou Wenlong]

In allocate_global_asid(), 'global_asid_available' cannot be zero, as it
has already been checked in use_global_asid(). Therefore, the warning in
allocate_global_asid() cannot be triggered; fix the wrong judgment in
allocate_global_asid().

Fixes: d504d1247e36 ("x86/mm: Add global ASID allocation helper functions")
Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>
---
 arch/x86/mm/tlb.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/x86/mm/tlb.c b/arch/x86/mm/tlb.c
index cad4a8eae2d8..e9eda296fb0e 100644
--- a/arch/x86/mm/tlb.c
+++ b/arch/x86/mm/tlb.c
@@ -319,7 +319,7 @@ static u16 allocate_global_asid(void)
 
 	asid = find_next_zero_bit(global_asid_used, MAX_ASID_AVAILABLE, last_global_asid);
 
-	if (asid >= MAX_ASID_AVAILABLE && !global_asid_available) {
+	if (asid >= MAX_ASID_AVAILABLE && global_asid_available) {
 		/* This should never happen. */
 		VM_WARN_ONCE(1, "Unable to allocate global ASID despite %d available\n",
 				global_asid_available);
-- 
2.31.1

Re: [PATCH 2/3] mm/tlb: Fix wrong judgement in allocate_global_asid()

[Rik van Riel]

On Sat, 2025-03-29 at 21:05 +0800, Hou Wenlong wrote:
> In allocate_global_asid(), 'global_asid_available' cannot be zero, as
> it
> has already been checked in use_global_asid(). Therefore, the warning
> in
> allocate_global_asid() cannot be triggered; fix the wrong judgment in
> allocate_global_asid().
> 
> Fixes: d504d1247e36 ("x86/mm: Add global ASID allocation helper
> functions")
> Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>

Good catch.

Reviewed-by: Rik van Riel <riel@surriel.com>


Looking at allocate_global_asid() again, I wonder if
that needs to be turned back into a loop.

What if we have no global asids available, and then
an asid gets freed that is smaller than the value
of last_global_asid?
-- 
All Rights Reversed.

Re: [PATCH 2/3] mm/tlb: Fix wrong judgement in allocate_global_asid()

[Hou Wenlong]

On Sun, Mar 30, 2025 at 01:33:44AM +0800, Rik van Riel wrote:
> On Sat, 2025-03-29 at 21:05 +0800, Hou Wenlong wrote:
> > In allocate_global_asid(), 'global_asid_available' cannot be zero, as
> > it
> > has already been checked in use_global_asid(). Therefore, the warning
> > in
> > allocate_global_asid() cannot be triggered; fix the wrong judgment in
> > allocate_global_asid().
> > 
> > Fixes: d504d1247e36 ("x86/mm: Add global ASID allocation helper
> > functions")
> > Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>
> 
> Good catch.
> 
> Reviewed-by: Rik van Riel <riel@surriel.com>
> 
> 
> Looking at allocate_global_asid() again, I wonder if
> that needs to be turned back into a loop.
> 
> What if we have no global asids available, and then
> an asid gets freed that is smaller than the value
> of last_global_asid?

Uh, I think this can be an easily triggered issue in the current code.
Moreover, reset_global_asid_space() is only called when 'last_global_asid'
is 'MAX_ASID_AVAILALBE-1', which means that free ASIDs are returned to
avaialable pool only in that case. So if the 'global_asid_used'
bitmap is full, but 'last_global_asid' is not 'MAX_ASID_AVIALBLE-1', the
allocation can fail as well. So I think the allocation may look like
this:
```
index 0f86c3140fdc..7f4bcb0e3d8c 100644
--- a/arch/x86/mm/tlb.c
+++ b/arch/x86/mm/tlb.c
@@ -312,17 +312,27 @@ static u16 allocate_global_asid(void)

        lockdep_assert_held(&global_asid_lock);

-       /* The previous allocation hit the edge of available address space */
-       if (last_global_asid >= MAX_ASID_AVAILABLE - 1)
-               reset_global_asid_space();
-
+       /* Search the range [last_global_asid, MAX_ASID_AVAILABLE-1]. */
        asid = find_next_zero_bit(global_asid_used, MAX_ASID_AVAILABLE, last_global_asid);
-
-       if (asid >= MAX_ASID_AVAILABLE && global_asid_available) {
-               /* This should never happen. */
-               VM_WARN_ONCE(1, "Unable to allocate global ASID despite %d available\n",
-                               global_asid_available);
-               return 0;
+       if (asid >= MAX_ASID_AVAILABLE) {
+               /* Search the range [TLB_NR_DYN_ASIDS, last_global_asid-1]. */
+               asid = find_next_zero_bit(global_asid_used, last_global_asid, TLB_NR_DYN_ASIDS);
+               if (asid >= last_global_asid) {
+                       /*
+                        * The 'global_asid_used' bitmap is full, so merge the
+                        * 'global_asid_freed' bitmap and search from the
+                        * beginning again.
+                        */
+                       reset_global_asid_space();
+                       asid = find_next_zero_bit(global_asid_used, MAX_ASID_AVAILABLE,
+                                                 last_global_asid);
+                       if (asid >= MAX_ASID_AVAILABLE && global_asid_available) {
+                               /* This should never happen. */
+                               VM_WARN_ONCE(1, "Unable to allocate global ASID despite %d available\n",
+                                               global_asid_available);
+                               return 0;
+                       }
+               }
        }
```

> -- 
> All Rights Reversed.

Re: [PATCH 2/3] mm/tlb: Fix wrong judgement in allocate_global_asid()

[Hou Wenlong]

On Mon, Mar 31, 2025 at 01:12:34PM +0800, Hou Wenlong wrote:
> On Sun, Mar 30, 2025 at 01:33:44AM +0800, Rik van Riel wrote:
> > On Sat, 2025-03-29 at 21:05 +0800, Hou Wenlong wrote:
> > > In allocate_global_asid(), 'global_asid_available' cannot be zero, as
> > > it
> > > has already been checked in use_global_asid(). Therefore, the warning
> > > in
> > > allocate_global_asid() cannot be triggered; fix the wrong judgment in
> > > allocate_global_asid().
> > > 
> > > Fixes: d504d1247e36 ("x86/mm: Add global ASID allocation helper
> > > functions")
> > > Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>
> > 
> > Good catch.
> > 
> > Reviewed-by: Rik van Riel <riel@surriel.com>
> > 
> > 
> > Looking at allocate_global_asid() again, I wonder if
> > that needs to be turned back into a loop.
> > 
> > What if we have no global asids available, and then
> > an asid gets freed that is smaller than the value
> > of last_global_asid?
> 
> Uh, I think this can be an easily triggered issue in the current code.
> Moreover, reset_global_asid_space() is only called when 'last_global_asid'
> is 'MAX_ASID_AVAILALBE-1', which means that free ASIDs are returned to
> avaialable pool only in that case. So if the 'global_asid_used'
> bitmap is full, but 'last_global_asid' is not 'MAX_ASID_AVIALBLE-1', the
> allocation can fail as well. So I think the allocation may look like
> this:
> ```
> index 0f86c3140fdc..7f4bcb0e3d8c 100644
> --- a/arch/x86/mm/tlb.c
> +++ b/arch/x86/mm/tlb.c
> @@ -312,17 +312,27 @@ static u16 allocate_global_asid(void)
> 
>         lockdep_assert_held(&global_asid_lock);
> 
> -       /* The previous allocation hit the edge of available address space */
> -       if (last_global_asid >= MAX_ASID_AVAILABLE - 1)
> -               reset_global_asid_space();
> -
> +       /* Search the range [last_global_asid, MAX_ASID_AVAILABLE-1]. */
>         asid = find_next_zero_bit(global_asid_used, MAX_ASID_AVAILABLE, last_global_asid);
> -
> -       if (asid >= MAX_ASID_AVAILABLE && global_asid_available) {
> -               /* This should never happen. */
> -               VM_WARN_ONCE(1, "Unable to allocate global ASID despite %d available\n",
> -                               global_asid_available);
> -               return 0;
> +       if (asid >= MAX_ASID_AVAILABLE) {
> +               /* Search the range [TLB_NR_DYN_ASIDS, last_global_asid-1]. */
> +               asid = find_next_zero_bit(global_asid_used, last_global_asid, TLB_NR_DYN_ASIDS);

Oh no, this doesn’t seem like it can happen, since we always search
starting from 'last_global_asid'. Even if there are free ASIDs that are
smaller than the value of 'last_global_asid', they will still be in the
'global_asid_freed' bitmap. Therefore, we need to call
reset_global_asid_space() directly here. I've looked back at your
patchset, and it seems that the original implementation before v6 is the
same as what I am describing here. I'm not sure why that was changed.

Additionally, I am wondering if it would be acceptable to remove the
'global_asid_freed' bitmap directly and clear the bit in the
'global_asid_used' bitmap instead. We could either search the range
[TLB_NR_DYN_ASIDS, MAX_ASID_AVAILABLE-1] or search the range
[global_asid_available, MAX_ASID_AVAILABLE-1] first, then search the
range [TLB_NR_DYN_ASIDS, global_asid_available-1]. This might simplify
the code.

--
Thanks!
> +               if (asid >= last_global_asid) {
> +                       /*
> +                        * The 'global_asid_used' bitmap is full, so merge the
> +                        * 'global_asid_freed' bitmap and search from the
> +                        * beginning again.
> +                        */
> +                       reset_global_asid_space();
> +                       asid = find_next_zero_bit(global_asid_used, MAX_ASID_AVAILABLE,
> +                                                 last_global_asid);
> +                       if (asid >= MAX_ASID_AVAILABLE && global_asid_available) {
> +                               /* This should never happen. */
> +                               VM_WARN_ONCE(1, "Unable to allocate global ASID despite %d available\n",
> +                                               global_asid_available);
> +                               return 0;
> +                       }
> +               }
>         }
> ```
> 
> > -- 
> > All Rights Reversed.

[PATCH 3/3] x86/mm: Fix wrong usage of 'MAX_ASID_AVAILABLE' in global ASID allocation

[Hou Wenlong]

'MAX_ASID_AVAILABLE' represents the maximum valid ASID in the current
definetion, meaning that the available ASID range is [0,
MAX_ASID_AVAILABLE]. So the actual count of available ASIDs is
'MAX_ASID_AVAIABLE + 1'. However, global ASID allocation use this value
as the size of the bitmap, which results in the maximum ASID number
being excluded from global ASID allocation. To address this issue,
redefine the 'MAX_ASID_AVAILABLE' as the count of available ASIDs.

Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>
---
 arch/x86/mm/tlb.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

diff --git a/arch/x86/mm/tlb.c b/arch/x86/mm/tlb.c
index e9eda296fb0e..0f86c3140fdc 100644
--- a/arch/x86/mm/tlb.c
+++ b/arch/x86/mm/tlb.c
@@ -102,18 +102,17 @@
 #define CR3_AVAIL_PCID_BITS (X86_CR3_PCID_BITS - PTI_CONSUMED_PCID_BITS)

 /*
- * ASIDs are zero-based: 0->MAX_AVAIL_ASID are valid.  -1 below to account
- * for them being zero-based.  Another -1 is because PCID 0 is reserved for
- * use by non-PCID-aware users.
+ * ASIDs are zero-based: 0->MAX_ASID_AVAILABLE-1 are valid.  -1 is because PCID
+ * 0 is reserved for use by non-PCID-aware users.
  */
-#define MAX_ASID_AVAILABLE ((1 << CR3_AVAIL_PCID_BITS) - 2)
+#define MAX_ASID_AVAILABLE ((1 << CR3_AVAIL_PCID_BITS) - 1)

 /*
  * Given @asid, compute kPCID
  */
 static inline u16 kern_pcid(u16 asid)
 {
-	VM_WARN_ON_ONCE(asid > MAX_ASID_AVAILABLE);
+	VM_WARN_ON_ONCE(asid >= MAX_ASID_AVAILABLE);

 #ifdef CONFIG_MITIGATION_PAGE_TABLE_ISOLATION
 	/*
--
2.31.1

Re: [PATCH 3/3] x86/mm: Fix wrong usage of 'MAX_ASID_AVAILABLE' in global ASID allocation

[Rik van Riel]

On Sat, 2025-03-29 at 21:05 +0800, Hou Wenlong wrote:
> 'MAX_ASID_AVAILABLE' represents the maximum valid ASID in the current
> definetion, meaning that the available ASID range is [0,
> MAX_ASID_AVAILABLE]. So the actual count of available ASIDs is
> 'MAX_ASID_AVAIABLE + 1'. However, global ASID allocation use this
> value
> as the size of the bitmap, which results in the maximum ASID number
> being excluded from global ASID allocation. To address this issue,
> redefine the 'MAX_ASID_AVAILABLE' as the count of available ASIDs.
> 
> Signed-off-by: Hou Wenlong <houwenlong.hwl@antgroup.com>

Reviewed-by: Rik van Riel <riel@surriel.com>

-- 
All Rights Reversed.