Breaking a node of link list

[Nehil]

i've following union

union header
{
struct
{
unsigned int size;
union header *next;
}s;

long x;
}

typedef union header Header;

i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

======================================================================

Now, ptr_free has size = 4096 bytes,

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

How can i do it??
plz give me a hint.

 

[Walter Roberson]

i've following union

union header
{
struct
{
unsigned int size;
union header *next;
}s;
long x;
}

typedef union header Header;

i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

Now, ptr_free has size = 4096 bytes,

It does??

Quoting from the Linux 2.4 sbrk() man page:

brk and sbrk are not defined in the C Standard and are deliberately
excluded from the POSIX.1 standard (see paragraphs B.1.1.1.3 and
B.8.3.3)

So here in comp.lang.c we don't know what the heck sbrk(4096) does.
And what it does might vary between different systems (that bother
to implement it at all) and between different versions of the same system.
So if your question depends upon some particular result being
returned by sbrk() then you need to take the question to a newsgroup
that deals with the OS or OSes that you need this to be portable to.

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

How can i do it??
plz give me a hint.

No can do unless you are the implementor of the processor architecture.
There are very few systems in which a pointer contains a size
*within the pointer itself* -- it would require a pointer representation
wider than the number of bits required to describe the largest object
size pointed to, and you would get wacky pointer semantics if you
did pointer arithmetic (and remember that pointer arithmetic must
be reversable...).

It would be possible to maintain the size of the nodes at the
location pointed *to*, but not practical in the pointer -itself-
("and in each pointer the size must be maintained").

Your union header has a size field, but you seem to be lacking
a field for the remaining storage in the node. Of course you have
a semantic problem in defining the type for that storage if you
are working in C89; in C99 you could type it as a VLA (Variable
Length Array).

 

[Nehil]

It does??

Quoting from the Linux 2.4 sbrk() man page:

brk and sbrk are not defined in the C Standard and are deliberately
excluded from the POSIX.1 standard (see paragraphs B.1.1.1.3 and
B.8.3.3)

So here in comp.lang.c we don't know what the heck sbrk(4096) does.
And what it does might vary between different systems (that bother
to implement it at all) and between different versions of the same system.
So if your question depends upon some particular result being
returned by sbrk() then you need to take the question to a newsgroup
that deals with the OS or OSes that you need this to be portable to.


No can do unless you are the implementor of the processor architecture.
There are very few systems in which a pointer contains a size
*within the pointer itself* -- it would require a pointer representation
wider than the number of bits required to describe the largest object
size pointed to, and you would get wacky pointer semantics if you
did pointer arithmetic (and remember that pointer arithmetic must
be reversable...).

It would be possible to maintain the size of the nodes at the
location pointed *to*, but not practical in the pointer -itself-
("and in each pointer the size must be maintained").

Your union header has a size field, but you seem to be lacking
a field for the remaining storage in the node. Of course you have
a semantic problem in defining the type for that storage if you
are working in C89; in C99 you could type it as a VLA (Variable
Length Array).

===================================================================

well, i agree that sbrk(int) is implementation defined, but don't u
think malloc must be using *something* like sbrk or brk to request the
memory chunk from OS.

or

do u know some poratble way of taking memory from OS? please tell me.

Now, let say i have a link list as follows :

header-->NODE1 => NODE2 => NODE3 => NODE4 => NULL

is there any way to merge the two nodes or to break a node in two
parts?

Please clarify.
Thanks.

 

[santosh]

well, i agree that sbrk(int) is implementation defined, but don't u
think malloc must be using *something* like sbrk or brk to request the
memory chunk from OS.

Not necessarily. There are situations where a host operating system
might not exist at all. In such cases malloc and friends would
presumably use system memory directly.

But the point is, whatever method malloc uses is system specific. C
runs on a huge variety of systems and hence it would not be feasible
for this group to discuss the details of all these systems. Hence only
Standard C is discussed here. Most major target platforms for C have
their own dedicated group, as do most major C compilers.

or

do u know some poratble way of taking memory from OS? please tell me.

Use malloc or calloc or realloc. Use free to deallocate.

Now, let say i have a link list as follows :

header-->NODE1 => NODE2 => NODE3 => NODE4 => NULL

is there any way to merge the two nodes or to break a node in two
parts?

Why do you need to do this? Nodes may exist at different memory
locations. What is it that you're doing that calls for "breaking" a
node or merging them?

 

[santosh]

i've following union

union header
{
struct
{
unsigned int size;
union header *next;
}s;

long x;
}

typedef union header Header;

i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

Now, ptr_free has size = 4096 bytes,

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

You cannot store sizes within pointers in Standard C. What you can do
is set ptr_free and ptr_alloc to point to the appropriate offsets
within the node and store the sizes is seperate variables. You could
encapsulate the pointer and it's associated size variable into a
structure. You can use the offsetof operator to get the offset of the
member where you want to "break" the node.

Why do you want to do this. This is probably going to be non-portable,
particularly if you try to access the separate parts of the union.

 

[Walter Roberson]

well, i agree that sbrk(int) is implementation defined, but don't u
think malloc must be using *something* like sbrk or brk to request the
memory chunk from OS.

Only for very loose definitions of "something like": in particular,
if you *define* _really_deep_malloc_magic() as being "something like
sbrk() or brk()" just on the basis that memory gets allocated
*somehow*, then yeah, of course. But the internals of malloc() differ
quite a bit between operating systems. The sbrk() semantics imply
that there is a linear "data space" that the operating system
appends onto the end of in order to satisfy allocation requests.
The reality might be very different for systems operating in
real memory mode, or for systems that use memory pools (different
allocation areas for different memory size requests).

One of the better known high performance malloc libraries for some
Unices uses mmap() requests against a base file descriptor open on
/dev/zero with copy-on-write semantics set; the mmap() requests get
mapped into some convenient place in the virtual memory space of the
process, potentially no-where near (in virtual space) anything else,
and potentially with "guard pages" to reduce the effect of overrunning
the allocated memory -- the important semantic detail of which
is that adjacent malloc() requests requiring new memory might
well not be virtually adjacent as implied by sbrk() semantics.

or

do u know some poratble way of taking memory from OS? please tell me.

malloc() and calloc(). Anything lower level is OS specific.

Now, let say i have a link list as follows :

header-->NODE1 => NODE2 => NODE3 => NODE4 => NULL

is there any way to merge the two nodes or to break a node in two
parts?

*If* you know that there was one big object which has been
sub-divided, then of course you can merge adjacent subdivisions
of it, or subdivide parts yourself. That's just standard linked
list manipulation, and the convenience of it depends upon
the representation and structures you used. The problems arise
if the objects you want to merge might not originally be part
of one original big object.

Are you trying to write your own memory allocator? If so, then
it would likely be a lot easier for you to find an allocator
that is already written. If you don't want to do that, then the
first thing you have to do, before you start worrying about linked
list manipulation, is to write up a list of the properties you
want the allocator to have. Is allocation speed the most important? Is
reducing memory fragmentation important? If allocation speed
is the most important, then is it permissible if the average case is
very fast, but the worst case is noticably slow? Does the user
of the allocator need to be able to use standard C pointers to point
into the allocated area, or are "array semantics" sufficient,
in which the use provides a base address and an offset and a routine
you provided gets or sets a value there? Because if you can get
away with "array semantics", then you can pause internally and
move memory around (e.g., pack fragments together to leave a bigger
free space) without worrying that something had a pointer to
memory and the next time they go to use the pointer, the underlying
value has moved. Etc., etc.. You have to decide on the crucial
design goals before you work on the internal representation.

 

[Nehil]

You cannot store sizes within pointers in Standard C. What you can do
is set ptr_free and ptr_alloc to point to the appropriate offsets
within the node and store the sizes is seperate variables. You could
encapsulate the pointer and it's associated size variable into a
structure. You can use the offsetof operator to get the offset of the
member where you want to "break" the node.

Why do you want to do this. This is probably going to be non-portable,
particularly if you try to access the separate parts of the union.

===================================================================

I've the following requirement :

i'm developing a Garbage Collector for C. so i'd do develop a complete
memory manager ie i'd to allocate and de-allocate. for allocation i'm
using sbrk(int mem).
acc. to man page it returns a void pointer to the memory chunk of mem
bytes. but actually it is returning a void pointer to a memory chunk
of 4kb (4096 bytes).
if the argument of sbrk is in between 1 and 4096 (including both ends)
the size of the chunk returned will be 4096 bytes.

Now, at the start of program this whole chunk can be treated as a free
block of memery. so i do as follows :

Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

when, user requests for memory of certain bytes, let say 20 byets. so
i do as follows : (i'm considering only the very 1st request)

ptr_alloc = ptr_free;
ptr_free = ptr_free + 20 + sizeof(Header);
void *memory = ptr_alloc + sizeof(Header);
return memory;

i.e. ptr_free is now pointing to the start of un-allocated part of
that big chunk. and memory points to the allocated part, but leaves
the starting header.

Now, ptr_free should have size of "rest of the block". but it is a
single node so it's not possible. plz correct me if i'm wrong.
To keep the record of free blocks i need to break the big chunk into
parts : Allocated and Free.
How can i break the node into two parts so that it can have size
information for allocated and free parts.

Hope u understand my question and problem.
Thanks.

 

[Nehil]

Only for very loose definitions of "something like": in particular,
if you *define* _really_deep_malloc_magic() as being "something like
sbrk() or brk()" just on the basis that memory gets allocated
*somehow*, then yeah, of course. But the internals of malloc() differ
quite a bit between operating systems. The sbrk() semantics imply
that there is a linear "data space" that the operating system
appends onto the end of in order to satisfy allocation requests.
The reality might be very different for systems operating in
real memory mode, or for systems that use memory pools (different
allocation areas for different memory size requests).

One of the better known high performance malloc libraries for some
Unices uses mmap() requests against a base file descriptor open on
/dev/zero with copy-on-write semantics set; the mmap() requests get
mapped into some convenient place in the virtual memory space of the
process, potentially no-where near (in virtual space) anything else,
and potentially with "guard pages" to reduce the effect of overrunning
the allocated memory -- the important semantic detail of which
is that adjacent malloc() requests requiring new memory might
well not be virtually adjacent as implied by sbrk() semantics.


malloc() and calloc(). Anything lower level is OS specific.



*If* you know that there was one big object which has been
sub-divided, then of course you can merge adjacent subdivisions
of it, or subdivide parts yourself. That's just standard linked
list manipulation, and the convenience of it depends upon
the representation and structures you used. The problems arise
if the objects you want to merge might not originally be part
of one original big object.

Are you trying to write your own memory allocator? If so, then
it would likely be a lot easier for you to find an allocator
that is already written. If you don't want to do that, then the
first thing you have to do, before you start worrying about linked
list manipulation, is to write up a list of the properties you
want the allocator to have. Is allocation speed the most important? Is
reducing memory fragmentation important? If allocation speed
is the most important, then is it permissible if the average case is
very fast, but the worst case is noticably slow? Does the user
of the allocator need to be able to use standard C pointers to point
into the allocated area, or are "array semantics" sufficient,
in which the use provides a base address and an offset and a routine
you provided gets or sets a value there? Because if you can get
away with "array semantics", then you can pause internally and
move memory around (e.g., pack fragments together to leave a bigger
free space) without worrying that something had a pointer to
memory and the next time they go to use the pointer, the underlying
value has moved. Etc., etc.. You have to decide on the crucial
design goals before you work on the internal representation.

Yes, I'm developing a garbage collector for C and thus have to do
memory allocation also. Then only i can keep the records that which
memory chunk is to be freed or not.
Plz refer to my reply to Mr.Santosh. I've explained my problem there.
Thakns.

 

[Walter Roberson]

I've the following requirement :

i'm developing a Garbage Collector for C. so i'd do develop a complete
memory manager ie i'd to allocate and de-allocate. for allocation i'm
using sbrk(int mem).

I am not clear what your portability requirements are? A number
of pointer operations which are formally unspecified or undefined
behaviour in C are well defined and simple if you are allowed to
assume particular operating environments -- but can be a large
large nuisance if you are trying to work portably.

acc. to man page it returns a void pointer to the memory chunk of mem
bytes. but actually it is returning a void pointer to a memory chunk
of 4kb (4096 bytes).

I'd like to emphasize that sbrk() is not considered portable,
being not a part of C nor of POSIX.1. It is part of the
Single Unix Specification Version 2, but there are still quite
a number of useful Unix operating systems which are not certified
to Version 2 of the SUS. Even the SUS lists them as LEGACY and says,
"The use of malloc() is now preferred because it can be used
portably with all other memory allocation functions and with any
function that uses other allocation functions."

http://www.opengroup.org/onlinepubs/007908799/xsh/brk.html

"It is unspecified whether the pointer returned by sbrk() is
aligned suitably for any purpose."

Which is equivilent to a flaming red arrow saying THIS IS NOT PORTABLE.

Now, at the start of program this whole chunk can be treated as a free
block of memery. so i do as follows :

Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

when, user requests for memory of certain bytes, let say 20 byets. so
i do as follows : (i'm considering only the very 1st request)

And if the user requests 4096 - sizeof(struct header) or more,
you have problems. The memory your allocation routines hands over
to the users must be consequative, so you cannot hand over multiple
chunks each with an embedded header.

ptr_alloc = ptr_free;
ptr_free = ptr_free + 20 + sizeof(Header);
void *memory = ptr_alloc + sizeof(Header);
return memory;

i.e. ptr_free is now pointing to the start of un-allocated part of
that big chunk. and memory points to the allocated part, but leaves
the starting header.

Now, ptr_free should have size of "rest of the block". but it is a
single node so it's not possible. plz correct me if i'm wrong.
To keep the record of free blocks i need to break the big chunk into
parts : Allocated and Free.
How can i break the node into two parts so that it can have size
information for allocated and free parts.

If you do not have enough C experience to figure this out on your
own (and it is not difficult) then you do not have enough C experience
to implement a garbage collector. This bit is trivial compared to
figuring out whether a particular block of memory is still in
use or not!