[ECOS] memory saving scheme for stacks

[ECOS] memory saving scheme for stacks

[Øyvind Harboe]

In my system I have a number of threads that typically do a bit of
processing and then long periods of sleep.

Since only one thread can run at any one time, there is lots of 
unused stack memory at any moment in time. This can be as much as 20% of
the overall memory in the system. Ignore SMP systems here.

A scheme to reclaim this memory comes to mind:

- When a thread is created, it is marked as being special:
"stacksaving-thread". SST for short.
- Only one SST thread runs at any one time.
- All SST share the same stack memory location.
- When SST thread is switched out, the portion of the stack that is in
use is saved off to a different memory location.
- When a SST thread is switched in, the portion of the stack that is in
use is restored from the saved off location.
- The threads in my system typically have 200-1000 bytes of stack in use
at any one time => memory copy shouldn't bring the system to its knees.

I'm sure this has been done before as I can't see anything that
indicates that this is impossible.


-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Nick Garnett]

Øyvind Harboe <oyvind.harboe@zylin.com> writes:

> In my system I have a number of threads that typically do a bit of
> processing and then long periods of sleep.
> 
> Since only one thread can run at any one time, there is lots of 
> unused stack memory at any moment in time. This can be as much as 20% of
> the overall memory in the system. Ignore SMP systems here.
> 
> A scheme to reclaim this memory comes to mind:
> 
> - When a thread is created, it is marked as being special:
> "stacksaving-thread". SST for short.
> - Only one SST thread runs at any one time.
> - All SST share the same stack memory location.
> - When SST thread is switched out, the portion of the stack that is in
> use is saved off to a different memory location.
> - When a SST thread is switched in, the portion of the stack that is in
> use is restored from the saved off location.
> - The threads in my system typically have 200-1000 bytes of stack in use
> at any one time => memory copy shouldn't bring the system to its knees.
> 
> I'm sure this has been done before as I can't see anything that
> indicates that this is impossible.

Wouldn't the save areas have to be as large as the stacks? Given that
the threads could be interrupted and preempted at any point and any
stack depth.

A better approach, would be to combine all these mostly idle threads
into one service thread that simply waits for one of several events
and services then as they arrive. But that does depend on the
structure of your threads.


-- 
Nick Garnett                    eCos Kernel Architect
http://www.ecoscentric.com/     The eCos and RedBoot experts


--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[sandeep]

Please see my comments inline. Correct me, if I am straying in understanding 
what you are proposing.

> In my system I have a number of threads that typically do a bit of
> processing and then long periods of sleep.
> 
> Since only one thread can run at any one time, there is lots of 
> unused stack memory at any moment in time. This can be as much as 20% of
> the overall memory in the system. Ignore SMP systems here.
> 
> A scheme to reclaim this memory comes to mind:
> 
> - When a thread is created, it is marked as being special:
> "stacksaving-thread". SST for short.
> - Only one SST thread runs at any one time.
> - All SST share the same stack memory location.
> - When SST thread is switched out, the portion of the stack that is in
> use is saved off to a different memory location.
where will be this memory location? Since this memory location has to be 
separate for each thread, and you stack could be maximum configured size at 
times during switching, you need to make sure enough size is reserved at your 
save location.

so where is your saving? the same amount of memory that you would have had as a 
stack, now you are going to have as savelocation. And w/o gaining what you 
intend to save, increasing the work at switching time.

> - When a SST thread is switched in, the portion of the stack that is in
> use is restored from the saved off location.
> - The threads in my system typically have 200-1000 bytes of stack in use
> at any one time => memory copy shouldn't bring the system to its knees.
In situations where you have many thread switchings, you would want to have 
context switching as fast as possible. Context-switch time is moreorless 
constant, above scheme will make it variable b/w a minimum and maximum 
(depending upon the maximum configured) stack size, can vary from configuration 
to configuration.

> I'm sure this has been done before as I can't see anything that
> indicates that this is impossible.
If whatever I mentioned above, holds out reasonable, then that explains why it 
might not have been done before, though not impossible.

-- 
regards
sandeep
--------------------------------------------------------------------------
"Every morning, I get up and look through the 'Forbes' list of the
richest people in America.  If I'm not there, I go to work"
		-- Robert Orben
--------------------------------------------------------------------------


-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

On Fri, 2004-07-23 at 12:03, Nick Garnett wrote:
> Øyvind Harboe <oyvind.harboe@zylin.com> writes:
> 
> > In my system I have a number of threads that typically do a bit of
> > processing and then long periods of sleep.
> > 
> > Since only one thread can run at any one time, there is lots of 
> > unused stack memory at any moment in time. This can be as much as 20% of
> > the overall memory in the system. Ignore SMP systems here.
> > 
> > A scheme to reclaim this memory comes to mind:
> > 
> > - When a thread is created, it is marked as being special:
> > "stacksaving-thread". SST for short.
> > - Only one SST thread runs at any one time.
> > - All SST share the same stack memory location.
> > - When SST thread is switched out, the portion of the stack that is in
> > use is saved off to a different memory location.
> > - When a SST thread is switched in, the portion of the stack that is in
> > use is restored from the saved off location.
> > - The threads in my system typically have 200-1000 bytes of stack in use
> > at any one time => memory copy shouldn't bring the system to its knees.
> > 
> > I'm sure this has been done before as I can't see anything that
> > indicates that this is impossible.
> 
> Wouldn't the save areas have to be as large as the stacks?

A large amount of the unused stack is allocated because there is no good
way of knowing how much stack is enough. With SST you allocate as much
stack as you think you need + 1*safety margin instead of n*safety
margin.

> Given that the threads could be interrupted and preempted at any point and any
> stack depth.

Fleshing out the idea a bit more:

Add a new kernel API where SST threads can indicate when they are
preemptable by other SST threads, i.e. when the thread usage is at its
lowest.

for (;;)
{
	// sleep here...

	cyg_thread_ss_suspend(); // do not let other SST threads run
	// do processing where stack usage is at its highest
	cyg_thread_ss_resume(); // let other SST threads run
}

> A better approach, would be to combine all these mostly idle threads
> into one service thread that simply waits for one of several events
> and services then as they arrive. But that does depend on the
> structure of your threads.

This is especially hard when the two threads cross modules, such as a
telnet + tftp thread.

-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

On Fri, 2004-07-23 at 12:19, sandeep wrote:
> Please see my comments inline. Correct me, if I am straying in understanding 
> what you are proposing.
> 
> > In my system I have a number of threads that typically do a bit of
> > processing and then long periods of sleep.
> > 
> > Since only one thread can run at any one time, there is lots of 
> > unused stack memory at any moment in time. This can be as much as 20% of
> > the overall memory in the system. Ignore SMP systems here.
> > 
> > A scheme to reclaim this memory comes to mind:
> > 
> > - When a thread is created, it is marked as being special:
> > "stacksaving-thread". SST for short.
> > - Only one SST thread runs at any one time.
> > - All SST share the same stack memory location.
> > - When SST thread is switched out, the portion of the stack that is in
> > use is saved off to a different memory location.
> where will be this memory location? Since this memory location has to be 
> separate for each thread, and you stack could be maximum configured size at 

It does not have to be seperate for each thread.

> times during switching, you need to make sure enough size is reserved at your 
> save location.

The area where the stack-in-use is saved off would have to be a shared
global memory area where the used stack is stored back-to-back. 
I believe that it is relatively straightforward matter to implement such
a storage facility, thus I haven't clouded my first explanation with
implementation issues. 

> > - When a SST thread is switched in, the portion of the stack that is in
> > use is restored from the saved off location.
> > - The threads in my system typically have 200-1000 bytes of stack in use
> > at any one time => memory copy shouldn't bring the system to its knees.
> In situations where you have many thread switchings, you would want to have 
> context switching as fast as possible. Context-switch time is moreorless 
> constant, above scheme will make it variable b/w a minimum and maximum 
> (depending upon the maximum configured) stack size, can vary from configuration 
> to configuration.

Obviously there is a CPU/memory tradeoff here. Each application will
have to figure out which threads should be SST and which should be
normal threads.

If you have the ram, then obviously SST threads make no sense.


-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[sandeep]

>>Given that the threads could be interrupted and preempted at any point and any
>>stack depth.
> Fleshing out the idea a bit more:
> 
> Add a new kernel API where SST threads can indicate when they are
> preemptable by other SST threads, i.e. when the thread usage is at its
> lowest.
how do you propose to decide when the thread usage is at it's lowest? - is only 
way for this is - the responsibility comes on the programmer to code accordingly.

but there are situations when SST can be moved out by another thread 
(SSI/normal) as a result of it's time slice getting over. The stack usage may 
not be at it's minimum then.

> 
> for (;;)
> {
> 	// sleep here...
> 
> 	cyg_thread_ss_suspend(); // do not let other SST threads run
> 	// do processing where stack usage is at its highest
> 	cyg_thread_ss_resume(); // let other SST threads run
> }

-- 
regards
sandeep
--------------------------------------------------------------------------
"Every morning, I get up and look through the 'Forbes' list of the
richest people in America.  If I'm not there, I go to work"
		-- Robert Orben
--------------------------------------------------------------------------


-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

On Fri, 2004-07-23 at 13:17, sandeep wrote:
> >>Given that the threads could be interrupted and preempted at any point and any
> >>stack depth.
> > Fleshing out the idea a bit more:
> > 
> > Add a new kernel API where SST threads can indicate when they are
> > preemptable by other SST threads, i.e. when the thread usage is at its
> > lowest.
> how do you propose to decide when the thread usage is at it's lowest? - is only 
> way for this is - the responsibility comes on the programmer to code accordingly.

The idea is to place the responsibility on the programmer to correctly
scatter cyg_thread_ss_suspend/resume() throughout the code.

> but there are situations when SST can be moved out by another thread 
> (SSI/normal) as a result of it's time slice getting over. The stack usage may 
> not be at it's minimum then.

When an SST thread is inside a cyg_thread_ss_suspend(), no other SST
threads will run until that thread invokes cyg_thread_ss_resume().

As with any sharp knife, you can hurt yourself by having a SST thread
inside cyg_thread_ss_suspend/resume() wait for another SST to complete
some task(such as releasing a mutex).

There are of course many other implementation issues to be sorted out,
but I can't see any trainwreckers. This is not a trivial thing to do,
but it might be worth it. 
 
> > for (;;)
> > {
> > 	// sleep here...
> > 
> > 	cyg_thread_ss_suspend(); // do not let other SST threads run
> > 	// do processing where stack usage is at its highest
> > 	cyg_thread_ss_resume(); // let other SST threads run
> > }
-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[sandeep]

> The area where the stack-in-use is saved off would have to be a shared
> global memory area where the used stack is stored back-to-back. 
> I believe that it is relatively straightforward matter to implement such
> a storage facility, thus I haven't clouded my first explanation with
> implementation issues.
Good, someone can continue from abstract end, and some on list can help the 
abstract thinker with the issues from the other (implementation) end.

U mean that not-executing threads' stacks will be adjacent to each other in some 
global pool.

? will this big pool be dynamically allocated? or pre-kept-aside

? what about the size of this big pool? wouldn't it be required to have it big 
enough to hold maximum saved stacks of all the non-executing threads? (since as 
of now i don't know if you have separate notions of SST and normal threads, see 
further for what i intend to ask by this). if that's the case then as much 
memory you have blocked as you would have by having N separate stacks (N = 
number of threads).

? i guess, this pre-kept-aside big pool will not be sufficient for cases where 
lots of threads may get created dynamically. you might not have any estimate of 
them beforehand - may be you once run under identical conditions to get some 
idea of it and use some margin.

? what i gather from your explanation, saved stacks will be looking like -
   ss1,ss2, ss3, ...,ssN

and the addresses of ss<i> is stored in corresponding thread structure (the 
length of this area could be either stored in first word of this area, or as a 
part of thread structure).

Now next time say, ss3 is loaded back. that will mean a hole in pool b/w ss2 and 
ss4. will this hole be used to store being-switched-out guy's stack? but it 
might not be sufficient size?

fragmentation will result in global pool that needs to be handled and needs 
additional compute/time resources.

? there is this issue of - do you check if enough space in pool to store the 
currently moved out guy's stack? say if not enough then what do you do? some 
sort memory compaction (this has further issues involved, if we go into this, 
then will blah blah on this).

btw, are you proposing to have two separate kind of threads - normal and SST ?
do you plan different treatments for them altogether from eCos? otherwise what 
will the use of two categories be, if SST is just like any normal thread apart 
from user writing the thread code in a way to decide where the thread could or 
couldn't be scheduled out.

and, SST will be making calls to rest of the eCos also, like normal threads. in 
that case notion of SST needs to be percolated throughout???

-- 
regards
sandeep
--------------------------------------------------------------------------
"Every morning, I get up and look through the 'Forbes' list of the
richest people in America.  If I'm not there, I go to work"
		-- Robert Orben
--------------------------------------------------------------------------


-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

On Fri, 2004-07-23 at 13:50, sandeep wrote:
> > The area where the stack-in-use is saved off would have to be a shared
> > global memory area where the used stack is stored back-to-back. 
> > I believe that it is relatively straightforward matter to implement such
> > a storage facility, thus I haven't clouded my first explanation with
> > implementation issues.
> Good, someone can continue from abstract end, and some on list can help the 
> abstract thinker with the issues from the other (implementation) end.
> 
> U mean that not-executing threads' stacks will be adjacent to each other in some 
> global pool.
> 
> ? will this big pool be dynamically allocated? or pre-kept-aside

allocated at startup time before SST threads are launched.

> 
> ? what about the size of this big pool? wouldn't it be required to have it big 
> enough to hold maximum saved stacks of all the non-executing threads?

Yes.

> (since as of now i don't know if you have separate notions of SST and normal threads, see 
> further for what i intend to ask by this). if that's the case then as much 
> memory you have blocked as you would have by having N separate stacks (N = 
> number of threads).

No.

The size of this buffer is the sum of the maximum stack usage outside
cyg_thread_ss_suspend/resume(), which it should be possible to determine
with great confidence.

The shared global stack amongst SST threads would have to be the size of
the maximum stack usage of SST threads.

> fragmentation will result in global pool that needs to be handled and needs 
> additional compute/time resources.

Certainly.

> btw, are you proposing to have two separate kind of threads - normal and SST ?

Yes.

> do you plan different treatments for them altogether from eCos?

No.

> otherwise what 
> will the use of two categories be, if SST is just like any normal thread apart 
> from user writing the thread code in a way to decide where the thread could or 
> couldn't be scheduled out.
> 
> and, SST will be making calls to rest of the eCos also, like normal threads. in 
> that case notion of SST needs to be percolated throughout???

As far as I can see, only SST threads needs to be aware of SST threads.
SST threads can make calls to eCos in the same fashion as normal
threads.

-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

[ECOS] Fis & JFFS2

[David Lewin]

Hi 

1/try to doing some files operations either to save some data.
Either on FIS or JFFS2, but how do I know what
is on ? I mean when doing a "mount" what FS is formated
on the flash ?

2/ I Also need to know what could 
"Cowardly refusing to erase blocks on filesystem with no valid JFFS2 nodes"
came from ?

Thanx in advance

-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

This is not something I *want* to do, but it is an avenue to pursue if 
we run out of RAM.


-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

> fragmentation will result in global pool that needs to be handled and needs 
> additional compute/time resources.

I just thought of something that is going to be important for my
application.

If a SST thread goes to sleep and the next SST thread to be reawaken is
that same thread, then no copying of stack is necessary => saves CPU.

-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Andrew Lunn]

> If you have the ram, then obviously SST threads make no sense.

It seems to me that nearly everything you have been doing for the last
couple of months has been to do with shoehorning your code into a
system with too little RAM. eCos is meant to be small, but it also has
to be clean, maintainable and efficient. 

It might be time to take a step back and take a look at your problem
from a wider angel. Consider how much time you have spent so far,
consider how much more time you would need to implement SST. Consider
the maintainance of such a system. Its always difficult to get a
stable system when you have extreamly tight memory since unexpected
things will happen in the field causing hard to reporduce bugs.

Talk to your hardware people and component supply people. It might
turn out cheaper in the long run to put bigger RAMs on the board and
save a huge amount of time and money on the software side of the
project.

        Andrew

-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] memory saving scheme for stacks

[Øyvind Harboe]

On Sun, 2004-08-01 at 22:52, Andrew Lunn wrote:
> > If you have the ram, then obviously SST threads make no sense.
> 
> It seems to me that nearly everything you have been doing for the last
> couple of months has been to do with shoehorning your code into a
> system with too little RAM. eCos is meant to be small, but it also has
> to be clean, maintainable and efficient. 
>
> It might be time to take a step back and take a look at your problem
> from a wider angel. Consider how much time you have spent so far,
> consider how much more time you would need to implement SST. Consider
> the maintainance of such a system. Its always difficult to get a
> stable system when you have extreamly tight memory since unexpected
> things will happen in the field causing hard to reporduce bugs.

Squeezing more out of the current system must of course be held up
against the costs of a redesign. At some point, doing a redesign is
cheaper.

> Talk to your hardware people and component supply people. It might
> turn out cheaper in the long run to put bigger RAMs on the board and
> save a huge amount of time and money on the software side of the
> project.

If they add DRAM(megabytes), word is we'll be switching to uCLinux. 

Hence the energy barrier(from a high-level perspective) to be crossed is
new board layout(which entails  more than just the CPU) + switching OS.

So far eCos has yielded to my efforts to squeeze a bit more out of the
system.

My current thinking on the SST stuff is that it is over the top.


>         Andrew
-- 
Øyvind Harboe
http://www.zylin.com



--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss