how to implement malloc without glibc, uclibc and kernel support

[miloody]

Dear all:
I try to cross-compile a program which runs standalone, no operating
system, on mips machine.
But the program is fulfilled with "malloc", which need c lib and
kernel support.
I know the implementation of malloc is quite complex and I want to
know does anyone have the same problem as me or is there any open
source which implement the same behavior of malloc already?
appreciate your help,
miloody

 

[Seebs]

Dear all:
I try to cross-compile a program which runs standalone, no operating
system, on mips machine.
But the program is fulfilled with "malloc", which need c lib and
kernel support.

Then don't use malloc in the standalone program.

I know the implementation of malloc is quite complex and I want to
know does anyone have the same problem as me or is there any open
source which implement the same behavior of malloc already?

Probably dozens. Obviously, there's glibc, bsd libc, and uclibc. I
suspect eCos has one too.

But I think you're probably thinking at entirely the wrong level. A
program which calls malloc is not a program which runs standalone
without an operating system, in general. How is this program supposed
to get any kind of input, or produce output?

In short: You can't run without an operating system. You might have
a program which IS its own operating system, but in that case, it had
better provide its own support code.

What you are doing has essentially nothing to do with C. You can't
implement malloc except in reference to the details of your operating
system -- and as noted above, there IS an operating system, even if
it ends up being contained in your program. Find a group specific
to your hardware platform or the environment from which you got a
compiler.

-s

 

[Keith Thompson]

I try to cross-compile a program which runs standalone, no operating
system, on mips machine.
But the program is fulfilled with "malloc", which need c lib and
kernel support.
I know the implementation of malloc is quite complex and I want to
know does anyone have the same problem as me or is there any open
source which implement the same behavior of malloc already?

Well, for starters, glibc is open source. I don't know whether its
malloc implementation is suitable for your purposes.

Is "malloc" really the only function that's causing problems?

(malloc should be easy to implement if you don't have to worry about
implementing free.)

 

[Chris McDonald]

Then don't use malloc in the standalone program.

But I think you're probably thinking at entirely the wrong level. A
program which calls malloc is not a program which runs standalone
without an operating system, in general. How is this program supposed
to get any kind of input, or produce output?

I think what the OP may be seeking is a version of "malloc" and friends
that manages allocation from, say, pre-reserved 1MB block of memory
(for example, not calling sbrk() under Unix).

 

[Seebs]

I think what the OP may be seeking is a version of "malloc" and friends
that manages allocation from, say, pre-reserved 1MB block of memory
(for example, not calling sbrk() under Unix).

That could be, and there are certainly a number of such things.

But...

In general, programs which are genuinely intended to run without an operating
system do not call a malloc() they don't include.

-s

 

[Seebs]

I think what the OP may be seeking is a version of "malloc" and friends
that manages allocation from, say, pre-reserved 1MB block of memory
(for example, not calling sbrk() under Unix).

That could be, and there are certainly a number of such things.

But...

In general, programs which are genuinely intended to run without an operating
system do not call a malloc() they don't include.

-s

 

[Nick Keighley]

Dear all:
I try to cross-compile a program which runs standalone, no operating
system, on mips machine.
But the program is fulfilled with "malloc", which need c lib and
kernel support.
I know the implementation of malloc is quite complex and I want to
know does anyone have the same problem as me or is there any open
source which implement the same behavior of malloc already?
appreciate your help,

you'll need to look at why the program is calling malloc().
Does it really have to? Can you replace the amlloc() calls with
arrays of pre-calculated size? If there are a small number
of them you might be able to get away with chopping up a
large block of memeory. What the other poster said "its easy
if don't need free" may well apply. Are all the calls the same
size but you just don't know how many there are (events, messages,
PDUs etc.)? Use a big array and mark the blocks as free or allocated.

 

[Nick Keighley]

Then don't use malloc in the standalone program.


Probably dozens.  Obviously, there's glibc, bsd libc, and uclibc.  I
suspect eCos has one too.

But I think you're probably thinking at entirely the wrong level.  A
program which calls malloc is not a program which runs standalone
without an operating system, in general.  How is this program supposed
to get any kind of input, or produce output?

In short:  You can't run without an operating system.  You might have
a program which IS its own operating system, but in that case, it had
better provide its own support code.

there are planty of run time support systems that I wouldn't call
an operating system

 

[Noob]

there are plenty of run time support systems that I wouldn't call
an operating system

e.g. MS-DOS

 

[Nick Keighley]

e.g. MS-DOS

actually I'm kind, I do describe DOS as a simple OS. It manages
resources
and schedules programs.

 

[Nick Keighley]

you'll need to look at why the program is calling malloc().
Does it really have to? Can you replace the amlloc() calls with
arrays of pre-calculated size? If there are a small number
of them you might be able to get away with chopping up a
large block of memeory. What the other poster said "its easy
if don't need free" may well apply. Are all the calls the same
size but you just don't know how many there are (events, messages,
PDUs etc.)? Use a big array and mark the blocks as free or allocated.

I've used systems that could receive arbitarily long messages.
The messages were stored internally as linked lists of fixed sized
blocks. There was a free list of unused blocks. Much easier
than a general purpose malloc(). If you really want to implement
malloc() go and look at heap algorithms.

 

[Chris M. Thomasson]

Dear all:
I try to cross-compile a program which runs standalone, no operating
system, on mips machine.
But the program is fulfilled with "malloc", which need c lib and
kernel support.
I know the implementation of malloc is quite complex and I want to
know does anyone have the same problem as me or is there any open
source which implement the same behavior of malloc already?
appreciate your help,

FWIW, I am quite fond of region allocators. Here is a simple example
implementation I created/hacked together:


http://pastebin.com/f37a23918


This allocator does not force all allocations to be aligned up to a
so-called maximum alignment like `malloc' and friends are required to do.
For instance, allocations for a single char will not be forced to waste the
extra alignment space. This can have benefits in space constrained
environments (e.g., embedded devices). Also, its static in nature and can be
fed with a buffer residing on the stack. There are no underlying calls to
`malloc'. This can be useful in free standing environments that do not
support heap allocation. One other thing. Its a pure region allocator which
means you do not need to free individual objects. You can free the entire
region. This is more efficient than calling `malloc()/free()' for each
object. For instance, you can destroy all the nodes in a linked list just by
freeing the region(s) in which the nodes were allocated from. There is no
need to traverse the list to free its nodes. Its a sort of "manual" garbage
collection... ;^)

You can use it like:
_________________________________________________________________
#include <ralloc.h>

struct foo {
struct foo* next;

};


#include <stdio.h>

void crunch() {
char local_buffer[1024];
struct region local_region;
struct foo* head1 = NULL;
struct foo* head2 = NULL;
size_t i, r;

rinit(&local_region, local_buffer, sizeof(local_buffer));

for (r = 0; r < 1024; ++r) {
size_t c = 0;

for (i = 0; i < 64; ++i) {
struct foo* foo = ralloct(&local_region, 2, struct foo);
if (foo) {
foo->next = head1;
head1 = foo;
++foo;
foo->next = head2;
head2 = foo;
c += 2;
}
}

while (head1) {
head1 = head1->next;
--c;
}

while (head2) {
head2 = head2->next;
--c;
}

assert(! c);

rflush(&local_region);
}

}


int main(void) {
crunch();
crunch();
crunch();
return 0;

}


_________________________________________________________________

IMVHO, that's kind of cool... ;^)

BTW, the alignment hack is fairly nasty! Try not to throw up to much...



This should be able to work in a standalone environment.

 

[Chris M. Thomasson]

FWIW, I am quite fond of region allocators. Here is a simple example
implementation I created/hacked together:

[...]

As for implementing malloc/free, well, you can do simple segregated storage
pool based allocator with non-fitting allocations flowing into a simple
counted region allocator.

 

[Chris M. Thomasson]

FWIW, I am quite fond of region allocators. Here is a simple example
implementation I created/hacked together:

[...]

As for implementing malloc/free, well, you can do simple segregated
storage pool based allocator with non-fitting allocations flowing into a
simple counted region allocator.

This can all be based on local memory (e.g., on the stack). Keep in mind
that it's perfectly okay for malloc to be based on static storage. malloc
can return NULL and, IMVHO, you're program should be robust enough to cope
with that fact...

 

[miloody]

Hi:
thanks for your help.

Then don't use malloc in the standalone program.


Probably dozens.  Obviously, there's glibc, bsd libc, and uclibc.  I
suspect eCos has one too.

But I think you're probably thinking at entirely the wrong level.  A
program which calls malloc is not a program which runs standalone
without an operating system, in general.  How is this program supposed
to get any kind of input, or produce output?

in general, you are correct.
But the situation I have is quite different.
Originally the code is running on arm system, and the debugging
environment of arm provides it's clib, not open source, to help on
malloc, free , printf and scanf, etc. without OS support.

Now I have to cross compile it on the sparc system, which don't have
such clib.
I try to remove malloc but it is to much that make it impossible.

I have write my own printf and scanf.

But malloc seems quite complex, it seems have to implement a heap and
manage which slot has been allocated and released.
I just try to find a func which is initialized by telling it the
starting address and size of free memory.
Then malloc it.

In short:  You can't run without an operating system.  You might have
a program which IS its own operating system, but in that case, it had
better provide its own support code.

What you are doing has essentially nothing to do with C.  You can't
implement malloc except in reference to the details of your operating
system -- and as noted above, there IS an operating system, even if
it ends up being contained in your program.  Find a group specific
to your hardware platform or the environment from which you got a
compiler.

appreciate your kind help
miloody

 

[miloody]

Hi:
thanks for your help.

Then don't use malloc in the standalone program.


Probably dozens.  Obviously, there's glibc, bsd libc, and uclibc.  I
suspect eCos has one too.

But I think you're probably thinking at entirely the wrong level.  A
program which calls malloc is not a program which runs standalone
without an operating system, in general.  How is this program supposed
to get any kind of input, or produce output?

in general, you are correct.
But the situation I have is quite different.
Originally the code is running on arm system, and the debugging
environment of arm provides it's clib, not open source, to help on
malloc, free , printf and scanf, etc. without OS support.

Now I have to cross compile it on the sparc system, which don't have
such clib.
I try to remove malloc but it is to much that make it impossible.

I have write my own printf and scanf.

But malloc seems quite complex, it seems have to implement a heap and
manage which slot has been allocated and released.
I just try to find a func which is initialized by telling it the
starting address and size of free memory.
Then malloc it.

In short:  You can't run without an operating system.  You might have
a program which IS its own operating system, but in that case, it had
better provide its own support code.

What you are doing has essentially nothing to do with C.  You can't
implement malloc except in reference to the details of your operating
system -- and as noted above, there IS an operating system, even if
it ends up being contained in your program.  Find a group specific
to your hardware platform or the environment from which you got a
compiler.

appreciate your kind help
miloody

 

[miloody]

Hi:
thanks for your help.

Then don't use malloc in the standalone program.


Probably dozens.  Obviously, there's glibc, bsd libc, and uclibc.  I
suspect eCos has one too.

But I think you're probably thinking at entirely the wrong level.  A
program which calls malloc is not a program which runs standalone
without an operating system, in general.  How is this program supposed
to get any kind of input, or produce output?

in general, you are correct.
But the situation I have is quite different.
Originally the code is running on arm system, and the debugging
environment of arm provides it's clib, not open source, to help on
malloc, free , printf and scanf, etc. without OS support.

Now I have to cross compile it on the sparc system, which don't have
such clib.
I try to remove malloc but it is to much that make it impossible.

I have write my own printf and scanf.

But malloc seems quite complex, it seems have to implement a heap and
manage which slot has been allocated and released.
I just try to find a func which is initialized by telling it the
starting address and size of free memory.
Then malloc it.

In short:  You can't run without an operating system.  You might have
a program which IS its own operating system, but in that case, it had
better provide its own support code.

What you are doing has essentially nothing to do with C.  You can't
implement malloc except in reference to the details of your operating
system -- and as noted above, there IS an operating system, even if
it ends up being contained in your program.  Find a group specific
to your hardware platform or the environment from which you got a
compiler.

appreciate your kind help
miloody

 

[Seebs]

in general, you are correct.
But the situation I have is quite different.
Originally the code is running on arm system, and the debugging
environment of arm provides it's clib, not open source, to help on
malloc, free , printf and scanf, etc. without OS support.

Uh, no.

The debugging environment provided you with a (however minimal) operating
system.

That's the key here -- the code which drives the hardware IS the OS, even
if it's a really lame OS.

Now I have to cross compile it on the sparc system, which don't have
such clib.

Uh.

You have code which runs on a given machine at a low enough level that
it's reasonable to think it would run without an OS.

You want to run it on another machine.

Why on earth do you think you can do this?

Does this program DO anything? Does it, at any time, accept some form of
input? Does it produce some form of output?

If so, either there is an operating system, or this program is doing so
through hard-coded direct access to the hardware.

If the former, well, there's your answer -- get a corresponding OS on the
sparc machine. If the latter, you're going to have to completely rewrite
all the code that does that input and output, in all probability.

I try to remove malloc but it is to much that make it impossible.

I have write my own printf and scanf.

But malloc seems quite complex, it seems have to implement a heap and
manage which slot has been allocated and released.
I just try to find a func which is initialized by telling it the
starting address and size of free memory.
Then malloc it.

There are functions similar to this in most C libraries, several of
which are available as free software under various licensing terms.
I'm pretty sure the BSD malloc/free could be tweaked relatively cheaply
to use a static block of available memory instead of system calls.

But think ahead a little further. Think about the I/O. If you can't
do the malloc part, I don't think you have good chances of dealing with
the problems you run into at execution time.

This is a really good time to start from scratch and, for instance, make
sure you understand all the critical code paths. How does input get accepted?
How similar is the corresponding hardware on the new box?

For that matter, how sure are you that you even have appropriate permission
to be doing this to this hunk of code? This sounds like the sort of thing
that might be part of a vendor SDK, and it may have licensing terms that
don't allow what you're doing.

-s

 

[Praveen]

Dear all:
I try to cross-compile a program which runs standalone, no operating
system, on mips machine.
But the program is fulfilled with "malloc", which need c lib and
kernel support.
I know the implementation of malloc is quite complex and I want to
know does anyone have the same problem as me or is there any open
source which implement the same behavior of malloc already?
appreciate your help,
miloody

http://www.embedded.com/design/opensource/209600563?printable=true
this link may help you.

 

[miloody]

Hi all:

implement the malloc function seen K&R2 should be good
(don't know if there is some copyright for the set of functions
 is there any copyright for that or for derivative from that?)

every programmer for me, has to implement that set of functions
(malloc, free, realloc etc) while seeing that code in K&R
it is instructive

thanks for your all kind help
miloody