[PATCH] ACPICA: Add hard limit to while loop

[PATCH] ACPICA: Add hard limit to while loop

[Alexey Starikovskiy]

We need to prevent infinite loops and lockups

Signed-off-by: Alexey Starikovskiy <astarikovskiy@suse.de>
---

 drivers/acpi/dispatcher/dsopcode.c |    9 +++++++--
 include/acpi/acstruct.h            |    1 +
 2 files changed, 8 insertions(+), 2 deletions(-)


diff --git a/drivers/acpi/dispatcher/dsopcode.c b/drivers/acpi/dispatcher/dsopcode.c
index 6a81c44..e2a3535 100644
--- a/drivers/acpi/dispatcher/dsopcode.c
+++ b/drivers/acpi/dispatcher/dsopcode.c
@@ -1246,8 +1246,13 @@ acpi_ds_exec_end_control_op(struct acpi_walk_state * walk_state,
 		if (walk_state->control_state->common.value) {
 
 			/* Predicate was true, go back and evaluate it again! */
-
-			status = AE_CTRL_PENDING;
+			/* Use hard limit to prevent infinite loops and lockups */
+			if (++walk_state->cycle_count > 0xFFFF) {
+				status = AE_LIMIT;
+				ACPI_ERROR ((AE_INFO, "Infinite loop detected"));
+			} else {
+				status = AE_CTRL_PENDING;
+			}
 		}
 
 		ACPI_DEBUG_PRINT((ACPI_DB_DISPATCH,
diff --git a/include/acpi/acstruct.h b/include/acpi/acstruct.h
index 7980a26..fb4405e 100644
--- a/include/acpi/acstruct.h
+++ b/include/acpi/acstruct.h
@@ -94,6 +94,7 @@ struct acpi_walk_state {
 	u32 method_breakpoint;	/* For single stepping */
 	u32 user_breakpoint;	/* User AML breakpoint */
 	u32 parse_flags;
+	u32 cycle_count;	/* While loop cycle count */
 
 	struct acpi_parse_state parser_state;	/* Current state of parser */
 	u32 prev_arg_types;

RE: [PATCH] ACPICA: Add hard limit to while loop

[Moore, Robert]

This sounds like a good idea.

I would probably add a new exception code so that it is clear exactly why the method was aborted, and make the maximum loop count a configuration constant.

Bob


-----Original Message-----
From: linux-acpi-owner@vger.kernel.org [mailto:linux-acpi-owner@vger.kernel.org] On Behalf Of Alexey Starikovskiy
Sent: Thursday, October 09, 2008 3:36 AM
To: LenBrown
Cc: Linux-acpi@vger.kernel.org
Subject: [PATCH] ACPICA: Add hard limit to while loop

We need to prevent infinite loops and lockups

Signed-off-by: Alexey Starikovskiy <astarikovskiy@suse.de>
---

 drivers/acpi/dispatcher/dsopcode.c |    9 +++++++--
 include/acpi/acstruct.h            |    1 +
 2 files changed, 8 insertions(+), 2 deletions(-)


diff --git a/drivers/acpi/dispatcher/dsopcode.c b/drivers/acpi/dispatcher/dsopcode.c
index 6a81c44..e2a3535 100644
--- a/drivers/acpi/dispatcher/dsopcode.c
+++ b/drivers/acpi/dispatcher/dsopcode.c
@@ -1246,8 +1246,13 @@ acpi_ds_exec_end_control_op(struct acpi_walk_state * walk_state,
                if (walk_state->control_state->common.value) {

                        /* Predicate was true, go back and evaluate it again! */
-
-                       status = AE_CTRL_PENDING;
+                       /* Use hard limit to prevent infinite loops and lockups */
+                       if (++walk_state->cycle_count > 0xFFFF) {
+                               status = AE_LIMIT;
+                               ACPI_ERROR ((AE_INFO, "Infinite loop detected"));
+                       } else {
+                               status = AE_CTRL_PENDING;
+                       }
                }

                ACPI_DEBUG_PRINT((ACPI_DB_DISPATCH,
diff --git a/include/acpi/acstruct.h b/include/acpi/acstruct.h
index 7980a26..fb4405e 100644
--- a/include/acpi/acstruct.h
+++ b/include/acpi/acstruct.h
@@ -94,6 +94,7 @@ struct acpi_walk_state {
        u32 method_breakpoint;  /* For single stepping */
        u32 user_breakpoint;    /* User AML breakpoint */
        u32 parse_flags;
+       u32 cycle_count;        /* While loop cycle count */

        struct acpi_parse_state parser_state;   /* Current state of parser */
        u32 prev_arg_types;

--
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: [PATCH] ACPICA: Add hard limit to while loop

[Moore, Robert]

The patch below will allow only 64K loop executions in a single control method, period -- regardless of the number of different loops or if there are nested loops. Do we really want this? Or do we want to implement it such that any single loop cannot execute more than 64K times?

To implement the limit on a strict per-while basis, the loop counter should be put into the walk_state->control_state. A control_state is allocated for each while.

Bob




>-----Original Message-----
>From: linux-acpi-owner@vger.kernel.org [mailto:linux-acpi-
>owner@vger.kernel.org] On Behalf Of Alexey Starikovskiy
>Sent: Thursday, October 09, 2008 3:36 AM
>To: LenBrown
>Cc: Linux-acpi@vger.kernel.org
>Subject: [PATCH] ACPICA: Add hard limit to while loop
>
>We need to prevent infinite loops and lockups
>
>Signed-off-by: Alexey Starikovskiy <astarikovskiy@suse.de>
>---
>
> drivers/acpi/dispatcher/dsopcode.c |    9 +++++++--
> include/acpi/acstruct.h            |    1 +
> 2 files changed, 8 insertions(+), 2 deletions(-)
>
>
>diff --git a/drivers/acpi/dispatcher/dsopcode.c
>b/drivers/acpi/dispatcher/dsopcode.c
>index 6a81c44..e2a3535 100644
>--- a/drivers/acpi/dispatcher/dsopcode.c
>+++ b/drivers/acpi/dispatcher/dsopcode.c
>@@ -1246,8 +1246,13 @@ acpi_ds_exec_end_control_op(struct acpi_walk_state *
>walk_state,
>                if (walk_state->control_state->common.value) {
>
>                        /* Predicate was true, go back and evaluate it
>again! */
>-
>-                       status = AE_CTRL_PENDING;
>+                       /* Use hard limit to prevent infinite loops and
>lockups */
>+                       if (++walk_state->cycle_count > 0xFFFF) {
>+                               status = AE_LIMIT;
>+                               ACPI_ERROR ((AE_INFO, "Infinite loop
>detected"));
>+                       } else {
>+                               status = AE_CTRL_PENDING;
>+                       }
>                }
>
>                ACPI_DEBUG_PRINT((ACPI_DB_DISPATCH,
>diff --git a/include/acpi/acstruct.h b/include/acpi/acstruct.h
>index 7980a26..fb4405e 100644
>--- a/include/acpi/acstruct.h
>+++ b/include/acpi/acstruct.h
>@@ -94,6 +94,7 @@ struct acpi_walk_state {
>        u32 method_breakpoint;  /* For single stepping */
>        u32 user_breakpoint;    /* User AML breakpoint */
>        u32 parse_flags;
>+       u32 cycle_count;        /* While loop cycle count */
>
>        struct acpi_parse_state parser_state;   /* Current state of parser
>*/
>        u32 prev_arg_types;
>
>--
>To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: [PATCH] ACPICA: Add hard limit to while loop

[Moore, Robert]

I can take this from here.

I see an opportunity here to implement a nice optimization for while loops. We currently allocate and free a control state for each iteration of the loop. This is overkill, we should just reuse the existing control state and only delete it when the loop terminates.

Once this is done, we can add the loop counter to the control state to implement a loop counter on a per-while basis.

Bob


>-----Original Message-----
>From: linux-acpi-owner@vger.kernel.org [mailto:linux-acpi-
>owner@vger.kernel.org] On Behalf Of Moore, Robert
>Sent: Thursday, October 09, 2008 7:56 AM
>To: Alexey Starikovskiy; LenBrown
>Cc: Linux-acpi@vger.kernel.org
>Subject: RE: [PATCH] ACPICA: Add hard limit to while loop
>
>The patch below will allow only 64K loop executions in a single control
>method, period -- regardless of the number of different loops or if there
>are nested loops. Do we really want this? Or do we want to implement it
>such that any single loop cannot execute more than 64K times?
>
>To implement the limit on a strict per-while basis, the loop counter should
>be put into the walk_state->control_state. A control_state is allocated for
>each while.
>
>Bob
>
>
>
>
>>-----Original Message-----
>>From: linux-acpi-owner@vger.kernel.org [mailto:linux-acpi-
>>owner@vger.kernel.org] On Behalf Of Alexey Starikovskiy
>>Sent: Thursday, October 09, 2008 3:36 AM
>>To: LenBrown
>>Cc: Linux-acpi@vger.kernel.org
>>Subject: [PATCH] ACPICA: Add hard limit to while loop
>>
>>We need to prevent infinite loops and lockups
>>
>>Signed-off-by: Alexey Starikovskiy <astarikovskiy@suse.de>
>>---
>>
>> drivers/acpi/dispatcher/dsopcode.c |    9 +++++++--
>> include/acpi/acstruct.h            |    1 +
>> 2 files changed, 8 insertions(+), 2 deletions(-)
>>
>>
>>diff --git a/drivers/acpi/dispatcher/dsopcode.c
>>b/drivers/acpi/dispatcher/dsopcode.c
>>index 6a81c44..e2a3535 100644
>>--- a/drivers/acpi/dispatcher/dsopcode.c
>>+++ b/drivers/acpi/dispatcher/dsopcode.c
>>@@ -1246,8 +1246,13 @@ acpi_ds_exec_end_control_op(struct acpi_walk_state
>*
>>walk_state,
>>                if (walk_state->control_state->common.value) {
>>
>>                        /* Predicate was true, go back and evaluate it
>>again! */
>>-
>>-                       status = AE_CTRL_PENDING;
>>+                       /* Use hard limit to prevent infinite loops and
>>lockups */
>>+                       if (++walk_state->cycle_count > 0xFFFF) {
>>+                               status = AE_LIMIT;
>>+                               ACPI_ERROR ((AE_INFO, "Infinite loop
>>detected"));
>>+                       } else {
>>+                               status = AE_CTRL_PENDING;
>>+                       }
>>                }
>>
>>                ACPI_DEBUG_PRINT((ACPI_DB_DISPATCH,
>>diff --git a/include/acpi/acstruct.h b/include/acpi/acstruct.h
>>index 7980a26..fb4405e 100644
>>--- a/include/acpi/acstruct.h
>>+++ b/include/acpi/acstruct.h
>>@@ -94,6 +94,7 @@ struct acpi_walk_state {
>>        u32 method_breakpoint;  /* For single stepping */
>>        u32 user_breakpoint;    /* User AML breakpoint */
>>        u32 parse_flags;
>>+       u32 cycle_count;        /* While loop cycle count */
>>
>>        struct acpi_parse_state parser_state;   /* Current state of parser
>>*/
>>        u32 prev_arg_types;
>>
>>--
>>To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
>>the body of a message to majordomo@vger.kernel.org
>>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>--
>To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: [PATCH] ACPICA: Add hard limit to while loop

[Len Brown]

Are AML while loops our only exposure to getting stuck interpreting AML 
forever?

Maybe there is a more general solution that would cover everything, such 
as counting opcodes or setting a watchdog timer?

thanks,
-Len

RE: [PATCH] ACPICA: Add hard limit to while loop

[Moore, Robert]

The mutex and event opcodes come to mind, the AML can wait forever on these (Acquire, Wait). However, the interpreter is released when these opcodes block, quite unlike a spinning while loop.

As far as infinite spin loops, I think While() is the only case. There is no GoTo AML operator, so loops cannot be artificially created.

So, I think the loop counter idea is ok. Of course, picking a maximum number might be a bit difficult. 64K loop iterations takes 4-5 seconds on my machine here (in Ring 3). That is a lot of loops for AML code, it might be ok.

Besides, we can say "nobody would ever need more than 64K loop iterations", and get ourselves in the computer hall of fame.  :-)

Bob


>-----Original Message-----
>From: Len Brown [mailto:lenb@kernel.org]
>Sent: Thursday, October 09, 2008 9:32 AM
>To: Moore, Robert
>Cc: Alexey Starikovskiy; Linux-acpi@vger.kernel.org
>Subject: RE: [PATCH] ACPICA: Add hard limit to while loop
>
>
>Are AML while loops our only exposure to getting stuck interpreting AML
>forever?
>
>Maybe there is a more general solution that would cover everything, such
>as counting opcodes or setting a watchdog timer?
>
>thanks,
>-Len

Re: [PATCH] ACPICA: Add hard limit to while loop

[Alexey Starikovskiy]

Moore, Robert wrote:
> The mutex and event opcodes come to mind, the AML can wait forever on these (Acquire, Wait). However, the interpreter is released when these opcodes block, quite unlike a spinning while loop.
>
> As far as infinite spin loops, I think While() is the only case. There is no GoTo AML operator, so loops cannot be artificially created.
>
> So, I think the loop counter idea is ok. Of course, picking a maximum number might be a bit difficult. 64K loop iterations takes 4-5 seconds on my machine here (in Ring 3). That is a lot of loops for AML code, it might be ok.
>
> Besides, we can say "nobody would ever need more than 64K loop iterations", and get ourselves in the computer hall of fame.  :-)
>
>   
Well, AML is not intended as general purpose OS/language, so we might be 
safe saying such things. :)
I would be extremely glad if Phoenix did not have enough 
resources/features to implement EC driver in AML in
first place :)

Regards,
Alex.

Re: [PATCH] ACPICA: Add hard limit to while loop

[Alexey Starikovskiy]

Moore, Robert wrote:
> I can take this from here.
>
> I see an opportunity here to implement a nice optimization for while loops. We currently allocate and free a control state for each iteration of the loop. This is overkill, we should just reuse the existing control state and only delete it when the loop terminates.
>
> Once this is done, we can add the loop counter to the control state to implement a loop counter on a per-while basis.
>
>   
Sounds great.
Thanks,
Alex.