Timing out LUA programs

classic Classic list List threaded Threaded
38 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Timing out LUA programs

davefowle
I am thinking of "embedding" LUA into my program,but I am concerned
about users writing "never ending" LUA programs.

Is there a safe way to shut down the LUA program after an arbitrary
time interval?

Regards

David Fowle



Reply | Threaded
Open this post in threaded view
|

RE: Timing out LUA programs

Nick Trout-4
> I am thinking of "embedding" LUA into my program,but I am concerned
> about users writing "never ending" LUA programs.
> 
> Is there a safe way to shut down the LUA program after an arbitrary
> time interval?

The same way you would in C. You can run for a set time then exit the Lua
state back to C and lua_close() or you could just call exit() in your code
depending on how you wanted to close down.

N


Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

paul winwood-3
In reply to this post by davefowle
--- In lua-l@y..., "davefowle" <davefowle@y...> wrote:
> Is there a safe way to shut down the LUA program after an arbitrary
> time interval?

I get the current time when I start the script running (lua_dofile, 
lua_dobuffer, etc.). Then I add a line hook and check the elapsed 
time. If the script runs for too long I call lua_error with an 
appropriate message which interrupts execution of the script.

Paul.


Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Luiz Henrique de Figueiredo
In reply to this post by davefowle
>> Is there a safe way to shut down the LUA program after an arbitrary
>> time interval?
>
>I get the current time when I start the script running (lua_dofile, 
>lua_dobuffer, etc.). Then I add a line hook and check the elapsed 
>time. If the script runs for too long I call lua_error with an 
>appropriate message which interrupts execution of the script.

Having a line hook always active can slow down your program. If your system
has support for timers or alarm you can set up a timer or alarm handler
and in it, when the event happens, set a line or call hook to handle the event. 
The lua.c interpreter does something similar to handle interrupts.

A sample implementation of alarm handling can be seen at
	ftp://ftp.tecgraf.puc-rio.br/pub/lhf/alarm.tar.gz
It needs signal and SIGALRM. It works with Lua 5.0w0 but with small changes
perhaps also in Lua 4.0.
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Reuben Thomas
> A sample implementation of alarm handling can be seen at
> 	ftp://ftp.tecgraf.puc-rio.br/pub/lhf/alarm.tar.gz

It would be really good if you could put pointers to things like this on
the Wiki (if you haven't already).

-- 
http://www.mupsych.org/rrt/ | The old cliches are the best


Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Thomas Wrensch-2
In reply to this post by davefowle
David,

Here's an approach to just this problem I've been considering for other
purposes. Please now that I have not done more than hack around a little
with this idea. It has the advantage of not using a linehook or a timer/
alarm.

The basic idea is to allocate a fixed number of bytecodes the user can
execute. Store a counter somewhere (if you're only using one state it
could be global, otherwise attach it to the lua state struct. Everytime
you execute a bytecode in luaV_execute (in lvm.c) decrement the counter.
When the counter is <= 0 you stop the program. I'm unsure just where the
counter should be checked, probably right in luaV_execute with an error
signaled if the counter runs to zero.

The two problems with this are (1) you can't be sure just how much time a
given number of bytecodes will execute and (2) it requires a fair amount
of messing around with the Lua internals. On the plus side the actual
lines of code you'd need to change are quite small for your application,
on the order of 10.

  - Tom Wrensch

On Tue, 18 Jun 2002, davefowle wrote:

> I am thinking of "embedding" LUA into my program,but I am concerned
> about users writing "never ending" LUA programs.
> 
> Is there a safe way to shut down the LUA program after an arbitrary
> time interval?
> 
> Regards
> 
> David Fowle
> 
> 
> 



Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Sean Middleditch
In reply to this post by davefowle
*cough*pre-emptive Lua threads w/ time quotas*cough*

Should I try starting another one of the pre-emptive vs. cooperative
threading debates, and throw in the point of killing threads as well?

Really, this feature should be simple to code in with the yield support
Lua already has.  Something running in the interpreter, and exit or
yield flag that could be set outside of the Lua bytecode.

Long running Lua threads could allow the embedding application to
continue running, or simply be killed off.

On Tue, 2002-06-18 at 03:56, davefowle wrote:
> I am thinking of "embedding" LUA into my program,but I am concerned
> about users writing "never ending" LUA programs.
> 
> Is there a safe way to shut down the LUA program after an arbitrary
> time interval?
> 
> Regards
> 
> David Fowle
> 
> 




Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Eric Tetz-2
--- Sean Middleditch <[hidden email]> wrote:
> *cough*pre-emptive Lua threads w/ time quotas*cough*
> 
> Should I try starting another one of the pre-emptive vs. cooperative
> threading debates, and throw in the point of killing threads as well?
> 
> Really, this feature should be simple to code in with the yield support
> Lua already has.

It already has:

http://www.tecgraf.puc-rio.br/~diego/luathreads/

> Long running Lua threads could allow the embedding application to
> continue running, or simply be killed off.

Off topic: anyone know how to "kill off a thread" safely in Windows?  There is a KillThread in the
API, but it definitely does not qualify as "safe".


__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com

Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Sean Middleditch
On Tue, 2002-06-18 at 13:12, Eric Tetz wrote:
> --- Sean Middleditch <[hidden email]> wrote:
> > *cough*pre-emptive Lua threads w/ time quotas*cough*
> > 
> > Should I try starting another one of the pre-emptive vs. cooperative
> > threading debates, and throw in the point of killing threads as well?
> > 
> > Really, this feature should be simple to code in with the yield support
> > Lua already has.
> 
> It already has:
> 
> http://www.tecgraf.puc-rio.br/~diego/luathreads/

Is this interface stable yet?  Also, what would the possibility of this
being merged into Lua proper be?  The lack of such a useful threading
implementation is the main reason I pulled Lua out of the projects I
originally used it in.  ^,^

> 
> > Long running Lua threads could allow the embedding application to
> > continue running, or simply be killed off.
> 
> Off topic: anyone know how to "kill off a thread" safely in Windows?  There is a KillThread in the
> API, but it definitely does not qualify as "safe".
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Yahoo! - Official partner of 2002 FIFA World Cup
> http://fifaworldcup.yahoo.com




Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Sean Middleditch
In reply to this post by Eric Tetz-2
( Sorry for double reply - I'm an idiot ~,^ )

Looking over the LuaThreads, it appears it makes use of the actual
system threads.

That's serious overkill, unefficient, etc.  When I want to run several
hundred AI threads, creating an OS thread simply won't work.  Plus, it's
not portable to embedded system that have no OS, or an OS without
threading support, etc.

Again, with Lua's co-threads support, it should be very easy (I would
imagine - haven't look at internals in a while) to make a
pre-emptive-ish threading system.  Simply do something akin to forced
yields, add in Lua mutex/semaphore data types, etc.  The main engine
would look at all available threads, and run each for X amount of time
or for X byte-code operations, then return to calling C code.  This way,
an application could launch Lua threads, and then have a
"lua_run_threads" call in the main update/event loop.

It *could* get even fancier by allowing a mixture of pre-emptable
threads and the current cooperative threads, plus a soft-pre-emptive. 
Soft pre-emptive would only pre-emptively switch on "safe" points, such
as when returning from a function call - this way, a given block of code
would be known to never be interrupted (making it easier to code for)
but you don't have to remember to sprinkle yield calls thru-out the
code.

You'd end up with a versatile threading solution that works in any way
needed (pre-emptive for large/complex tasks, cooperative for simple
tasks/generators, etc.), and even allowing both types of threading in
the same application without recompilation or major hacking.

On Tue, 2002-06-18 at 13:12, Eric Tetz wrote:
> --- Sean Middleditch <[hidden email]> wrote:
> > *cough*pre-emptive Lua threads w/ time quotas*cough*
> > 
> > Should I try starting another one of the pre-emptive vs. cooperative
> > threading debates, and throw in the point of killing threads as well?
> > 
> > Really, this feature should be simple to code in with the yield support
> > Lua already has.
> 
> It already has:
> 
> http://www.tecgraf.puc-rio.br/~diego/luathreads/
> 
> > Long running Lua threads could allow the embedding application to
> > continue running, or simply be killed off.
> 
> Off topic: anyone know how to "kill off a thread" safely in Windows?  There is a KillThread in the
> API, but it definitely does not qualify as "safe".
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Yahoo! - Official partner of 2002 FIFA World Cup
> http://fifaworldcup.yahoo.com




Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Edgar Toernig
In reply to this post by Luiz Henrique de Figueiredo
Luiz Henrique de Figueiredo wrote:
> 
> Having a line hook always active can slow down your program. If your system
> has support for timers or alarm you can set up a timer or alarm handler
> and in it, when the event happens, set a line or call hook to handle the event.
> The lua.c interpreter does something similar to handle interrupts.

Be careful.  Afaics lua_setlinehook/lua_setcallhook are no longer signal save.
They may deadlock due to lua_lock.  And setlinehook seems to depend on
complex data structures which may not be stable during a signal handler.
It becomes tricky...

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Thomas Wrensch-2
In reply to this post by Sean Middleditch
Sean,

On 18 Jun 2002, Sean Middleditch wrote:

> Again, with Lua's co-threads support, it should be very easy (I would
> imagine - haven't look at internals in a while) to make a
> pre-emptive-ish threading system.  Simply do something akin to forced
> yields, add in Lua mutex/semaphore data types, etc.  The main engine
> would look at all available threads, and run each for X amount of time
> or for X byte-code operations, then return to calling C code.  This way,
> an application could launch Lua threads, and then have a
> "lua_run_threads" call in the main update/event loop.

This is what I'm working on with the "count the byte codes" idea. I'm
trying to see how easy it is and how ugly the implementation will be.
If it seems possible to easily implement a lightweight preemptive
system this way, I'll report it to the list.

  - Tom


Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Björn De Meyer
In reply to this post by Sean Middleditch
Sean Middleditch wrote:
> 
> Again, with Lua's co-threads support, it should be very easy (I would
> imagine - haven't look at internals in a while) to make a
> pre-emptive-ish threading system.  Simply do something akin to forced
> yields, add in Lua mutex/semaphore data types, etc.  The main engine
> would look at all available threads, and run each for X amount of time
> or for X byte-code operations, then return to calling C code.  This way,
> an application could launch Lua threads, and then have a
> "lua_run_threads" call in the main update/event loop.

Well, that could be helpful. Such a Lua would still block when calling 
the C functions, though. Contrary to what I said before, there is no 
truly correct and portable way to do coroutines in plain ANSI C. 
You need system-dependent extensions, and then we're even farther from
home,
so to speak.

On the other hand, it might be the question why you would use a separate 
"microthread" for each and every agent in an AI system. Simply looping 
over all agents in a big (timed) loop, or using some kind
of message passing and/or callbacks can be just as efficient,
not to mention a lot simpler, as you have no pains with mutexes and
semaphores.

-- 
"No one knows true heroes, for they speak not of their greatness." -- 
Daniel Remar.
Björn De Meyer 
[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Sean Middleditch
On Tue, 2002-06-18 at 14:27, Björn De Meyer wrote:
> Sean Middleditch wrote:
> > 
> > Again, with Lua's co-threads support, it should be very easy (I would
> > imagine - haven't look at internals in a while) to make a
> > pre-emptive-ish threading system.  Simply do something akin to forced
> > yields, add in Lua mutex/semaphore data types, etc.  The main engine
> > would look at all available threads, and run each for X amount of time
> > or for X byte-code operations, then return to calling C code.  This way,
> > an application could launch Lua threads, and then have a
> > "lua_run_threads" call in the main update/event loop.
> 
> Well, that could be helpful. Such a Lua would still block when calling 
> the C functions, though. Contrary to what I said before, there is no 
> truly correct and portable way to do coroutines in plain ANSI C. 
> You need system-dependent extensions, and then we're even farther from
> home,
> so to speak.

Yes, there is a problem with threading inside of C functions.  That has
to be handled generally with a less than optimal way - i.e., requiring C
functions to be coded specially for threading (allow them to return with
a status code, then recalled with the status code to let them know where
they broke off, and the function would have to check for a "context
switch" state after every Lua call that could trigger such a switch -
would this not be similar to a C function calling a co-thread that then
yields tho?), or disable threading when there is a C function on the Lua
call stack.

> 
> On the other hand, it might be the question why you would use a separate 
> "microthread" for each and every agent in an AI system. Simply looping 
> over all agents in a big (timed) loop, or using some kind
> of message passing and/or callbacks can be just as efficient,
> not to mention a lot simpler, as you have no pains with mutexes and
> semaphores.

If I have 200 active agents, for example, even a very small AI script
will eat up a few milliseconds - that equates to about 400 milliseconds
per frame just for AI, and that is with a very simple AI.  With a
pre-emptive system, larger AI tasks (ones that have a lot of logic or
math in them) will be auto-matically broken up.  Plus, a good script
schedular would be able to decide to only call a limited number of
threads per lua_run_threads() call, so one frame 20 agents are updated,
next frame the next 20 agents, etc.

One wouldn't want to just replace cooperative threading tho (I finally
found a use for stuff ^,^ ) since it good for animation scripting:

move_to (1.5, 2.0, 4.5)
face_direction (NORTH)
target = nearest_enemy ()

... etc.

The long and short of it is that callbacks are not sufficient for
immersive behaviour scripting.  Plus, any scripting language used needs
to be capable of intelligently scaling down the amount of processing it
does per frame, by breaking up tasks or multi-frame scheduling.

This is yet another reason so many game authors keep writing their own
scripting language - no complete freely available language I know of
handles this intelligently.  Especially when you are writing a game that
customers are allowed to modify/script, where you have non-professionals
who don't know how to optimize efficiently.

> 
> -- 
> "No one knows true heroes, for they speak not of their greatness." -- 
> Daniel Remar.
> Björn De Meyer 
> [hidden email]




Reply | Threaded
Open this post in threaded view
|

Re: Timing out LUA programs

Sean Middleditch
In reply to this post by Thomas Wrensch-2
On Tue, 2002-06-18 at 14:18, Tom Wrensch wrote:
> Sean,
> 
> On 18 Jun 2002, Sean Middleditch wrote:
> 
> > Again, with Lua's co-threads support, it should be very easy (I would
> > imagine - haven't look at internals in a while) to make a
> > pre-emptive-ish threading system.  Simply do something akin to forced
> > yields, add in Lua mutex/semaphore data types, etc.  The main engine
> > would look at all available threads, and run each for X amount of time
> > or for X byte-code operations, then return to calling C code.  This way,
> > an application could launch Lua threads, and then have a
> > "lua_run_threads" call in the main update/event loop.
> 
> This is what I'm working on with the "count the byte codes" idea. I'm
> trying to see how easy it is and how ugly the implementation will be.
> If it seems possible to easily implement a lightweight preemptive
> system this way, I'll report it to the list.

Ah.  I have such a system in use on Scriptix.  I'm also planning on
getting it to work with signal alarms, too, for time-based threading
(which can be more efficient - a single "operator" may be a call into a
C function, which could take up a significant amount of time).

> 
>   - Tom
> 




Reply | Threaded
Open this post in threaded view
|

RE: Timing out LUA programs

Jeff Petkau
In reply to this post by davefowle
> On the other hand, it might be the question why you would use a separate 
> "microthread" for each and every agent in an AI system. Simply looping 
> over all agents in a big (timed) loop, or using some kind
> of message passing and/or callbacks can be just as efficient,
> not to mention a lot simpler, as you have no pains with mutexes and
> semaphores.

The reason is simple. With a microthread per agent, scripts look
something like this:

function dostuff()
  walk_to(A)
  wait(10)
  walk_to(B)
  if (something_happened()) then
    do_this()
  else
    do_that()
  end
end

If you don't have microthreads, you have to manage state explicitly,
and they often look like this:

# states...
INIT=0
WALKING_TO_A=1
WAITING=2
WALKING_TO_B=3
DOING_SOMETHING=4

function update_state()
  if (state==INIT) then
    state=WALKING_TO_A
    start_walk_to(A)

  elseif (state==WALKING_TO_A) then
    if walk_done() then
      state=WAITING
      start_wait(10)
    end

  elseif (state==WAITING) then
    if wait_done() then
      state=WALKING_TO_B
      start_walk_to(B)
    end

  elseif (state==WALKING_TO_B) then
    if walk_done() then
      if (something_happened()) then
        start_doing_this()
        state = DOING_SOMETHING
      else
        start_doing_that()
        state = DOING_SOMETHING
      end
    end

  elseif (state==DOING_SOMETHING) then
    if (finished_something()) then
      set_flag_saying_this_task_finished()
      return
    end
  end
end

Obviously there are different ways to approach this, some
of them cleaner for certain problems, but it still comes
out to a coding style where your only flow control is a
'goto' and if you want a stack you have to manage it
yourself.

--Jeff

Reply | Threaded
Open this post in threaded view
|

A good hash algorithm

Martin Hollis-2
In reply to this post by Sean Middleditch
I stumbled across this link:

http://burtleburtle.net/bob/hash/doobs.html

which claims to include a good hash algorithm. I know the hashing in lua is supposed to be excellent, but I thought I'd point it out anyway and let the lua authors evaluate the well presented claims on the page.

I quote:

"
Abstract
I offer you a new hash function for hash table lookup that is faster and more
thorough than the one you are using now. I also give you a way to verify that it is
more thorough.

...

Conclusion
A common weakness in hash function is for a small set of input bits to cancel each
other out. There is an efficient test to detect most such weaknesses, and many
functions pass this test. I gave code for the fastest such function I could find.
Hash functions without this weakness work equally well on all classes of keys.
"


Martin.


Reply | Threaded
Open this post in threaded view
|

Re: A good hash algorithm

Luiz Henrique de Figueiredo
>let the lua authors evaluate the well presented claims on the page.

Perhaps a kind soul has the time for this. If someone comes up with a better
hash algorithm than the one used in Lua and has established that it is better
in Lua, we'd be happy to consider adding it to the code, but please make sure
that it's not slower than the current one.
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: A good hash algorithm

RLak
In reply to this post by Martin Hollis-2
>>let the lua authors evaluate the well presented claims on the page.

> Perhaps a kind soul has the time for this. If someone comes up with a
better
> hash algorithm than the one used in Lua and has established that it is
better
> in Lua, we'd be happy to consider adding it to the code, but please make
sure
> that it's not slower than the current one.

I'm not volunteering to do that :)

One of the interesting things about the Lua hash algorithm (aside from the
fact that it doesn't depend on the 32-bitness of integers) is that it is
time-bounded for long strings -- there is a maximum on the number of
characters hashed. This may strike people like the author of the cited
algorithm as inferior, but one needs to balance costs. The "best" hash
algorithm is not necessarily the fastest in actual practice.

Consider the case of a hash-table with 20 keys, each of which is a string
of a million bytes. A "really good" hash algorithm would probably succeed
in creating a unique hash for each string, but in O(1,000,000) time. The
Lua hash algorithm might hash all of them onto the same value; the cost of
that would be that the table lookup would be essentially linear, or O(20).
In practice, scanning 20 table entries on each lookup is probably faster
than computing 20 hashes of a million bytes, unless there are a lot of
lookups.

Here's my S/0.02 contribution to Lua hashes, though (and I haven't looked
at v5 yet, so ignore me if you've done this):

Once a string is interned into the string hash table, its address becomes a
unique identifier. So there are two alternatives: use the hash as
originally computed as the string's lookup hash, or use the address as with
any other allocated object. If the original hash is sub-ideal, the address
may be a better lookup hash.

The objection might arise that there are not many random bits in a malloc'd
address. This is true: neither the high-order nor the low-order bits are
random. However, there are probably as many random bits as the log of the
number of elements in the largest table, because objects will be randomly
scattered around allocated memory, and allocated memory is larger the the
largest table. Consequently, dropping the last four bits or so of the
address and then using the rest as a hash value is likely to be pretty
good. (If I'm not mistaken, currently three bits are dropped, but four
would be better for malloc's that like to 16-byte align things.)

Rici



Reply | Threaded
Open this post in threaded view
|

Re: A good hash algorithm

Steve Dekorte-4

On Tuesday, June 18, 2002, at 12:51  PM, [hidden email] wrote:
Consider the case of a hash-table with 20 keys, each of which is a string of a million bytes. A "really good" hash algorithm would probably succeed
in creating a unique hash for each string, but in O(1,000,000) time. The
Lua hash algorithm might hash all of them onto the same value; the cost of that would be that the table lookup would be essentially linear, or O(20).
In practice, scanning 20 table entries on each lookup is probably faster
than computing 20 hashes of a million bytes, unless there are a lot of
lookups.

But don't you still need to do a O(1,000,000) string compare on potentially each of the 20 strings?

Steve



12