Prev: Parsing in Embedded Systems
Next: usb device cable is unrecognized by pc
From: D Yuniskis on 2 Mar 2010 13:06
Hi,

[no idea why I bother including c.realtime as it's deader'n a
doornail, there! :< ]

I'm thinking of implementing a "wait until satisfied"
option in malloc() [call it by some other name soas not
to muddy the typical expectations of malloc(3)].
In essence, if malloc() *would* return NULL, it,
instead, *blocks* waiting for the Heap to be able to
satisfy the request.

The first (naive) strategy I considered was to block all
future malloc()'s -- i.e., don't let anything else be
withdrawn from the heap -- and only allow free()'s to
proceed. *Naive* in that it assumes the resources the
first caller awaits are going to be released "soon".

*Dangerous* in that it is rife with potential for deadlock! :<

So, the only realistic implementation is to allow malloc()
and free() to proceed unimpeded. However, I can hook all
free()'s so the blocked request(s) is reissued prior to
return-ing.

I've not decided if the free() should then preempt the current
task or simply perform the deferred allocation and return
to its caller. I also haven't decided how to handle multiple
requests (queue based on task priority? size?)

[Note that this can be implemented efficiently and need not
bear the cost of an embedded "malloc()"-like invocation.]

Notice that the behavior blocking-for-request differs from
moving this activity up to the caller (i.e., call malloc,
get NULL, lather/rinse/repeat).

Are there any other issues that I am missing? Or, dragons to
be wary of?

Thanks!
--don
From: Vladimir Vassilevsky on 2 Mar 2010 13:07

Trying to reinvent Java?

VLV


D Yuniskis wrote:

> Hi,
>
> [no idea why I bother including c.realtime as it's deader'n a
> doornail, there! :< ]
>
> I'm thinking of implementing a "wait until satisfied"
> option in malloc() [call it by some other name soas not
> to muddy the typical expectations of malloc(3)].
> In essence, if malloc() *would* return NULL, it,
> instead, *blocks* waiting for the Heap to be able to
> satisfy the request.
>
> The first (naive) strategy I considered was to block all
> future malloc()'s -- i.e., don't let anything else be
> withdrawn from the heap -- and only allow free()'s to
> proceed. *Naive* in that it assumes the resources the
> first caller awaits are going to be released "soon".
>
> *Dangerous* in that it is rife with potential for deadlock! :<
>
> So, the only realistic implementation is to allow malloc()
> and free() to proceed unimpeded. However, I can hook all
> free()'s so the blocked request(s) is reissued prior to
> return-ing.
>
> I've not decided if the free() should then preempt the current
> task or simply perform the deferred allocation and return
> to its caller. I also haven't decided how to handle multiple
> requests (queue based on task priority? size?)
>
> [Note that this can be implemented efficiently and need not
> bear the cost of an embedded "malloc()"-like invocation.]
>
> Notice that the behavior blocking-for-request differs from
> moving this activity up to the caller (i.e., call malloc,
> get NULL, lather/rinse/repeat).
>
> Are there any other issues that I am missing? Or, dragons to
> be wary of?
>
> Thanks!
> --don
From: D Yuniskis on 2 Mar 2010 13:27
Hi Vladimir,

Vladimir Vassilevsky wrote:

> Trying to reinvent Java?

<grin> No. Just trying to promote to the interface layer
anything that the application can't "emulate" in some other
way. :-/
From: Tim Wescott on 2 Mar 2010 14:48
D Yuniskis wrote:
> Hi,
>
> [no idea why I bother including c.realtime as it's deader'n a
> doornail, there! :< ]
>
> I'm thinking of implementing a "wait until satisfied"
> option in malloc() [call it by some other name soas not
> to muddy the typical expectations of malloc(3)].
> In essence, if malloc() *would* return NULL, it,
> instead, *blocks* waiting for the Heap to be able to
> satisfy the request.

So if my code _could_ gracefully deal with not being able to get data
I'm still screwed? Gee, thanks.

> The first (naive) strategy I considered was to block all
> future malloc()'s -- i.e., don't let anything else be
> withdrawn from the heap -- and only allow free()'s to
> proceed. *Naive* in that it assumes the resources the
> first caller awaits are going to be released "soon".

So if your code wants 10000 bytes and mine needs 10 I'm screwed? Gee,
thanks.

> *Dangerous* in that it is rife with potential for deadlock! :<
>
> So, the only realistic implementation is to allow malloc()
> and free() to proceed unimpeded. However, I can hook all
> free()'s so the blocked request(s) is reissued prior to
> return-ing.
>
> I've not decided if the free() should then preempt the current
> task or simply perform the deferred allocation and return
> to its caller. I also haven't decided how to handle multiple
> requests (queue based on task priority? size?)
>
> [Note that this can be implemented efficiently and need not
> bear the cost of an embedded "malloc()"-like invocation.]
>
> Notice that the behavior blocking-for-request differs from
> moving this activity up to the caller (i.e., call malloc,
> get NULL, lather/rinse/repeat).
>
> Are there any other issues that I am missing? Or, dragons to
> be wary of?

I hope that you're planning on a "blockable malloc" and a "plain ol'
malloc". Better, put the "engineer" in "software engineer" and design
your system to not use the heap.

If you're going to make a blockable malloc, you should probably also
prioritize the malloc, so that malloc requests from higher priority
tasks get first choice of what's available.

But I think you're better off just not using malloc at all unless you
don't care about the system being real time.

--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
From: D Yuniskis on 2 Mar 2010 16:31
Hi Tim,

Tim Wescott wrote:
> D Yuniskis wrote:
>>
>> I'm thinking of implementing a "wait until satisfied"
>> option in malloc() [call it by some other name soas not
>> to muddy the typical expectations of malloc(3)].
>> In essence, if malloc() *would* return NULL, it,
>> instead, *blocks* waiting for the Heap to be able to
>> satisfy the request.
>
> So if my code _could_ gracefully deal with not being able to get data
> I'm still screwed? Gee, thanks.

Perhaps you neglected to read: "... OPTION in malloc..."
Presumably, the designer knows when *to* invoke said
option and when *not* to.

>> The first (naive) strategy I considered was to block all
>> future malloc()'s -- i.e., don't let anything else be
>> withdrawn from the heap -- and only allow free()'s to
>> proceed. *Naive* in that it assumes the resources the
>> first caller awaits are going to be released "soon".
>
> So if your code wants 10000 bytes and mine needs 10 I'm screwed? Gee,
> thanks.

You'll note I abandoned this idea.

And, in the idea proposed (below), your allocation could still be
satisfied -- unless it competes overtly with "mine".

In *any* allotment of resources, there are winners and losers.
If you *need* your "10" (always), then you can either (you being
the developer):
- declare it static
- allocate an arena (heap) for the exclusive use of your task/thread
- coordinate (implicitly or explicitly) your use of a shared
resource to ensure (by design) that you can fulfill this need
- add more re$ource$ to the device

>> *Dangerous* in that it is rife with potential for deadlock! :<
>>
>> So, the only realistic implementation is to allow malloc()
>> and free() to proceed unimpeded. However, I can hook all
>> free()'s so the blocked request(s) is reissued prior to
>> return-ing.
>>
>> I've not decided if the free() should then preempt the current
>> task or simply perform the deferred allocation and return
>> to its caller. I also haven't decided how to handle multiple
>> requests (queue based on task priority? size?)
>>
>> [Note that this can be implemented efficiently and need not
>> bear the cost of an embedded "malloc()"-like invocation.]
>>
>> Notice that the behavior blocking-for-request differs from
>> moving this activity up to the caller (i.e., call malloc,
>> get NULL, lather/rinse/repeat).
>>
>> Are there any other issues that I am missing? Or, dragons to
>> be wary of?
>
> I hope that you're planning on a "blockable malloc" and a "plain ol'
> malloc". Better, put the "engineer" in "software engineer" and design
> your system to not use the heap.

Again, "option".

Not all systems can be designed a priori with static allocation.
Or, if they are, they end up using more resources (or have fewer
options) that they would, otherwise.

> If you're going to make a blockable malloc, you should probably also
> prioritize the malloc, so that malloc requests from higher priority
> tasks get first choice of what's available.
>
> But I think you're better off just not using malloc at all unless you
> don't care about the system being real time.

It is a fallacy to assume that malloc precludes real-time
system designs. That sort of argument extends to imply that
you can't design a real-time system with a network stack.
Or a serial port. Or any other "thing" that can't be
deterministically controlled in the development effort.

As with any RT design, you carefully decide which actions
*require* deterministic responses; which of those are HRT
vs. SRT; and which things can be done "as available". You
can also design the system so that it *handles* missed
deadlines gracefully -- even rearranging the workload to
prevent such overruns from happening in the future.

E.g., crt0 brings up the RTOS. Do *all* of the objects used
by the RTOS have to be statically defined? Is there something
that recludes building task contexts from the system heap
(instead of declaring them as static)? Is there something
that precludes creating per-thread stacks from that heap?
Is there something that precludes creating per-thread
*heaps* from that heap?

Depriving yourself of a tool (e.g., the Heap) is something
you should only do if you *know* it won't work -- or, if you
can't figure out how to craft your application to use it
effectively within the constraints imposed by it. It's
like deciding *universally* not to use long doubles
"because they are too slow"...
 |  Next  |  Last
Pages: 1 2 3 4
Prev: Parsing in Embedded Systems
Next: usb device cable is unrecognized by pc