Internal implementation of realloc

[Kislay]

How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?

[Ian Collins]

Kislay wrote:

How is realloc implemented internally ?

The same answers that were given to the earlier thread 'printf' apply.

--
Ian Collins.

[pete]

Kislay wrote:

How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ?

Copied.

In the second case , wouldn't this method be inefficient if the old
region was large ?

It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.

Expanding a linked list to N nodes,
would more likely be an O(N) operation.

--
pete

[Malcolm McLean]

"Kislay" <ki***********@gmail.comwrote in message

How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?

Pseudo code

get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block

You can implement a rather inefficient realloc() with simply a
getblocksize() function. If you can peek into the internals of the malloc(0
system, you can extend the blocks if possible, which avoids the copy.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Richard Tobin]

In article <Vp******************************@earthlink.com> ,
pete <pf*****@mindspring.comwrote:

>In the second case , wouldn't this method be inefficient if the old
region was large ?

>It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.

If you can find any real implementation with this behaviour,
I'll be very surprised.

-- Richard
--
Please remember to mention me / in tapes you leave behind.

[ediebur]

On Sep 3, 3:41*pm, "Malcolm McLean" <[e-mail]:

"Kislay" <[e-mail] in message

How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?

Pseudo code

get block size
get space after block
if(blocksize + space < new blocksize)
* adjust block
else
* * allocate new block
* * copy data
* * free old block

You can implement a rather inefficient realloc() with simply a
getblocksize() function. If you can peek into the internals of the malloc(0
system, you can extend the blocks if possible, which avoids the copy.

--
Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

It has been a long, long time since I looked at the code but I believe
that some sort of realloc is the basic mechanism for buffer managment
in emacs-- I could be wrong

[pete]

Richard Tobin wrote:

In article <Vp******************************@earthlink.com> ,
pete <pf*****@mindspring.comwrote:

>>In the second case , wouldn't this method be inefficient if the old
region was large ?

>It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.

If you can find any real implementation with this behaviour,
I'll be very surprised.

I was thinking of a situation where the array becomes
expanded as the data comes in, ultimately to N elements;
not a situation where realloc is called only once.

That's the situation with the typical use of
Richard Heathfield's fgetline function at
http://www.cpax.org.uk/prg/writings/fgetline.c

That's also the situation with the typical use of my get_line function
http://www.mindspring.com/~pfilandr/...ine/get_line.c

and also with the evil Dr. Sosman's getline function,
http://www.cpax.org.uk/prg/portable/...sman/index.php

It makes sense to me that as the array grows,
each subsequent realloc should take proportionally longer.
And that when you have K*N allocations,
the total building of the N element array
becomes an O(N*N) operation.

--
pete

[Gene]

On Sep 3, 8:43*pm, pete <[e-mail]:

Richard Tobin wrote:

In article <[e-mail]> ,
pete *<[e-mail]:

>In the second case , wouldn't this method be inefficient if the old
region was large ?

It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.

If you can find any real implementation with this behaviour,
I'll be very surprised.

I was thinking of a situation where the array becomes
expanded as the data comes in, ultimately to N elements;
not a situation where realloc is called only once.

That's the situation with the typical use of
Richard Heathfield's fgetline function athttp://www.cpax.org.uk/prg/writings/fgetline.c

That's also the situation with the typical use of my get_line functionhttp://www.mindspring.com/~pfilandr/C/get_line/get_line.c

and also with the evil Dr. Sosman's getline function,http://www.cpax.org.uk/prg/portable/...sman/index.php

It makes sense to me that as the array grows,
each subsequent realloc should take proportionally longer.
And that when you have K*N allocations,
the total building of the N element array
becomes an O(N*N) operation.

This is why nearly all code for expanding an array "on demand"
_multiplies_ the size of the array by a factor greater than 1 (2 being
very popular) rather than adding a constant. It isn't hard to prove
that the amortized cost of copying with this method is O(N) for an
array that has grown to size N.

[Eric Sosman]

Malcolm McLean wrote:

>
"Kislay" <ki***********@gmail.comwrote in message

>How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?

Pseudo code

get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block

It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. Market forces
seem to favor a higher QoI.

--
Eric Sosman
es*****@ieee-dot-org.invalid

[Richard Tobin]

In article <Da******************************@earthlink.com> ,
pete <pf*****@mindspring.comwrote:

>>It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.

>If you can find any real implementation with this behaviour,
I'll be very surprised.

>I was thinking of a situation where the array becomes
expanded as the data comes in, ultimately to N elements;
not a situation where realloc is called only once.

So was I.

You would get your N^2 behaviour if every realloc() required copying,
or if a fixed fraction of them did. But a sensible implementation
will not work like that. It will allocate in such a way that there is
more spare space with large allocations.

If the block sizes it uses increase by a constant factor (power-of-two
is a special case of this), then the copying required will be such
that it's still O(N).

-- Richard
--
Please remember to mention me / in tapes you leave behind.

[Malcolm McLean]

"Eric Sosman" <es*****@ieee-dot-org.invalidwrote in message

>
It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. Market forces
seem to favor a higher QoI.

I've implemented realloc() like that. On an embedded platform it's often the
best you can do.
There are other tricks. For instance if memory is paged it might be possible
to remap the page addresses without physically copying data. However that
can't be done in standard C, and not on every platform.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Eric Sosman]

Malcolm McLean wrote:

>
"Eric Sosman" <es*****@ieee-dot-org.invalidwrote in message

>>
It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. Market forces
seem to favor a higher QoI.

I've implemented realloc() like that. On an embedded platform it's often
the best you can do.
There are other tricks. For instance if memory is paged it might be
possible to remap the page addresses without physically copying data.
However that can't be done in standard C, and not on every platform.

You've overlooked a fairly important use of realloc():

char *ptr = malloc(1073741824);
...
char *new = realloc(ptr, 1);

Your implementation uses a gigabyte (or so) to store one byte
of "payload." No others I've seen have been so wasteful.

--
Eric Sosman
es*****@ieee-dot-org.invalid

[Stephen Sprunk]

Eric Sosman wrote:

Malcolm McLean wrote:

>>
"Kislay" <ki***********@gmail.comwrote in message

>>How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?

Pseudo code

get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block

It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. Market forces
seem to favor a higher QoI.

That's how I assumed realloc() was normally implemented; logically,
that's what it appears to do...

While probably not what you're thinking of, I've seen a simple realloc()
implementation in a book that _always_ relocated the block. The purpose
was to help diagnose intermittent errors that were caused by callers
forgetting that realloc() _could_ relocate the block because, in some
circumstances, it is a rare occurrence.

S

[Keith Thompson]

Eric Sosman <es*****@ieee-dot-org.invalidwrites:

Malcolm McLean wrote:

>"Eric Sosman" <es*****@ieee-dot-org.invalidwrote in message

>>>
It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. Market forces
seem to favor a higher QoI.

I've implemented realloc() like that. On an embedded platform it's
often the best you can do.
There are other tricks. For instance if memory is paged it might be
possible to remap the page addresses without physically copying
data. However that can't be done in standard C, and not on every
platform.

You've overlooked a fairly important use of realloc():

char *ptr = malloc(1073741824);
...
char *new = realloc(ptr, 1);

Your implementation uses a gigabyte (or so) to store one byte
of "payload." No others I've seen have been so wasteful.

Malcolm's pseudo code was:

get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block

I assumed the "adjust block" would include shrinking the allocated
space, making the unused portion available.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Gene]

On Sep 4, 3:22*pm, "Malcolm McLean" <[e-mail]:

"Eric Sosman" <[e-mail] in message

* * It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. *Market forces
seem to favor a higher QoI.

There are other tricks. For instance if memory is paged it might be possible
to remap the page addresses without physically copying data. However that
can't be done in standard C, and not on every platform.

This occurred to me, too.

If you think about it, though, it won't work unless malloc()
cooperates. The expansion takes place in _virtual memory space_ not
physical. I.e. if malloc() hands out blocks that are contiguous in
virtual space, remapping won't help because when you try to grow a
block, malloc() has probably already given up the virtual addresses
immediately above.

Now 64-bit addresses open a new possibility. If every malloc (at
least up up to 4 billion of them) returns an address with the lower
(say) 32-bits zero, then every block can be grown to 4gb by remapping
pages.

With 32-bit addresses, the possibilities are less exciting: e.g. up to
64K of mallocs() that can each be expanded up to 64kb. Not good for
the general case, but perhaps for special ones...

[CBFalconer]

Stephen Sprunk wrote:

>

.... snip ...

>
While probably not what you're thinking of, I've seen a simple
realloc() implementation in a book that _always_ relocated the
block. The purpose was to help diagnose intermittent errors that
were caused by callers forgetting that realloc() _could_ relocate
the block because, in some circumstances, it is a rare occurrence.

To the contrary, because moving the storage implies moving the
data, which may be long and time consuming, some malloc packages go
to special efforts to avoid any moves, and thus modification of the
pointer to the block. You can see the source of such a package at:

<http://cbfalconer.home.att.net/download/nmalloc.zip>

written for the DJGPP system. Very little need be done to adapt it
to most systems.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Chris Torek]

>On Sep 4, 3:22*pm, "Malcolm McLean" <[e-mail]:

>>... if memory is paged it might be possible to [implement realloc()
via] remap[ping] the page addresses without physically copying data.

In article <2a**********************************@w7g2000hsa.g ooglegroups.com>,
Gene <ge**********@gmail.comwrote:

>This occurred to me, too.

If you think about it, though, it won't work unless malloc()
cooperates.

Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

>The expansion takes place in _virtual memory space_ not
physical. I.e. if malloc() hands out blocks that are contiguous in
virtual space, remapping won't help because when you try to grow a
block, malloc() has probably already given up the virtual addresses
immediately above.

This is not a problem, because the caller must write:

original_region = malloc(original_size); /* called O and S below */
... do appropriate work with it ...
new_region = realloc(original, new_size); /* called N and T below */

The realloc() call can obtain any available (and suitable, if there
are restrictions) set of virtual addresses, then ask the OS to move
the physical pages from the old address-space -- the region underlying
the virtual address range in [O..O+S-1] -- to the new range [N..N+T-1]
(with "new" pages added at the end if needed, or "old" pages removed
if T < S; and of course S and T are page-rounded and O and N must be
page-aligned).

If the pages are *moved* (as opposed to simply multiply-mapped),
this also gives you a Feature: subsequent access to original_region[i]
will fail ("segfault" or "bus error" or whatever), which will help
the programmer find any "stale" pointers. This technique is quite
useful for debugging, and hence doing page-moving into "fresh"
virtual space on *every* memory allocation -- even those that can
be done without such a move -- can be valuable. Similarly, one
can unmap the page(s) backing any region that has been free()d.

(I used this trick to find a bug in the 4.3BSD kernel once.)

>Now 64-bit addresses open a new possibility. If every malloc (at
least up up to 4 billion of them) returns an address with the lower
(say) 32-bits zero, then every block can be grown to 4gb by remapping
pages.

If you parcel out virtual addresses on 4GB boundaries, you can
expand in-place even *without* page-remapping. (Well, assuming
the physical page size is less than 4GB, at least. :-) )
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: gmail (figure it out) http://web.torek.net/torek/index.html

[CBFalconer]

Chris Torek wrote:

Gene <ge**********@gmail.comwrote:

>"Malcolm McLean" <[e-mail]:

>>... if memory is paged it might be possible to [implement realloc()
via] remap[ping] the page addresses without physically copying data.

This occurred to me, too. If you think about it, though, it
won't work unless malloc() cooperates.

Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

What __vmalloc and __pagealloc functions? No such thing in std C.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Eric Sosman]

CBFalconer wrote:

Chris Torek wrote:

>Gene <ge**********@gmail.comwrote:

>>"Malcolm McLean" <[e-mail]:

... if memory is paged it might be possible to [implement realloc()
via] remap[ping] the page addresses without physically copying data.
This occurred to me, too. If you think about it, though, it
won't work unless malloc() cooperates.

Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

What __vmalloc and __pagealloc functions? No such thing in std C.

Typos: Chris actually meant _vmalloc() and _pagealloc().

--
Eric Sosman
es*****@ieee-dot-org.invalid

[CBFalconer]

Eric Sosman wrote:

CBFalconer wrote:

>Chris Torek wrote:

>>Gene <ge**********@gmail.comwrote:
"Malcolm McLean" <[e-mail]:

... if memory is paged it might be possible to [implement
realloc() via] remap[ping] the page addresses without
physically copying data.

This occurred to me, too. If you think about it, though, it
won't work unless malloc() cooperates.

Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

What __vmalloc and __pagealloc functions? No such thing in std C.

Typos: Chris actually meant _vmalloc() and _pagealloc().

I still don't find those names, with or without leading '_', in the
standard.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Ian Collins]

CBFalconer wrote:

Eric Sosman wrote:

>CBFalconer wrote:

>>Chris Torek wrote:
Gene <ge**********@gmail.comwrote:
"Malcolm McLean" <[e-mail]:
>
>... if memory is paged it might be possible to [implement
>realloc() via] remap[ping] the page addresses without
>physically copying data.
This occurred to me, too. If you think about it, though, it
won't work unless malloc() cooperates.
Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)
What __vmalloc and __pagealloc functions? No such thing in std C.

Typos: Chris actually meant _vmalloc() and _pagealloc().

I still don't find those names, with or without leading '_', in the
standard.

Isn't it obvious from the context what they do? It's hard to tell if
you are being dense or obtuse.

--
Ian Collins.

[Keith Thompson]

CBFalconer <cb********@yahoo.comwrites:

Eric Sosman wrote:

>CBFalconer wrote:

>>Chris Torek wrote:
Gene <ge**********@gmail.comwrote:
"Malcolm McLean" <[e-mail]:
>
>... if memory is paged it might be possible to [implement
>realloc() via] remap[ping] the page addresses without
>physically copying data.
>
This occurred to me, too. If you think about it, though, it
won't work unless malloc() cooperates.

Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

What __vmalloc and __pagealloc functions? No such thing in std C.

Typos: Chris actually meant _vmalloc() and _pagealloc().

I still don't find those names, with or without leading '_', in the
standard.

I'm 99.99% certain that Chris Torek is aware of that -- and that's
probably an underestimate.

Replacing one or more of the standard library functions causes
undefined behavior. Chris was illustrating one way in which that
undefined behavior can manifest itself as things going badly wrong
rather than as things working as one might naively expect. Think of
_vmalloc() and _pagealloc() as *examples* of things within the
internals of a standard library implementation that can cause problems
when you start mucking around with replacements for standard library
functions.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[CBFalconer]

Keith Thompson wrote:

CBFalconer <cb********@yahoo.comwrites:

>Eric Sosman wrote:

>>CBFalconer wrote:
Chris Torek wrote:
Gene <ge**********@gmail.comwrote:
>"Malcolm McLean" <[e-mail]:
>>
>>... if memory is paged it might be possible to [implement
>>realloc() via] remap[ping] the page addresses without
>>physically copying data.
>>
>This occurred to me, too. If you think about it, though, it
>won't work unless malloc() cooperates.
>
Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

What __vmalloc and __pagealloc functions? No such thing in std C.

Typos: Chris actually meant _vmalloc() and _pagealloc().

I still don't find those names, with or without leading '_', in the
standard.

I'm 99.99% certain that Chris Torek is aware of that -- and that's
probably an underestimate.

Replacing one or more of the standard library functions causes
undefined behavior. Chris was illustrating one way in which that
undefined behavior can manifest itself as things going badly wrong
rather than as things working as one might naively expect. Think of
_vmalloc() and _pagealloc() as *examples* of things within the
internals of a standard library implementation that can cause problems
when you start mucking around with replacements for standard library
functions.

If you qualify it like that, fine. There are simpler illustrations
of the dangers of replacing malloc. For example, it may be used in
the initialization code, and prelinked there.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

[Eric Sosman]

CBFalconer wrote:

Eric Sosman wrote:

>CBFalconer wrote:

>>Chris Torek wrote:
Gene <ge**********@gmail.comwrote:
"Malcolm McLean" <[e-mail]:
>
>... if memory is paged it might be possible to [implement
>realloc() via] remap[ping] the page addresses without
>physically copying data.
This occurred to me, too. If you think about it, though, it
won't work unless malloc() cooperates.
Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)
What __vmalloc and __pagealloc functions? No such thing in std C.

Typos: Chris actually meant _vmalloc() and _pagealloc().

I still don't find those names, with or without leading '_', in the
standard.

Ah, but you *do* find it stated that those names -- with
a single leading _ -- are "reserved for any use." Hence, a
portable C program cannot observe whether they are or are not
defined. That which is not observable cannot be forbidden,
nor even described.

See also _flsbuf().

--
Eric Sosman
es*****@ieee-dot-org.invalid

[Malcolm McLean]

"CBFalconer" <cb********@yahoo.comwrote in message

Stephen Sprunk wrote:

>>

... snip ...

>>
While probably not what you're thinking of, I've seen a simple
realloc() implementation in a book that _always_ relocated the
block. The purpose was to help diagnose intermittent errors that
were caused by callers forgetting that realloc() _could_ relocate
the block because, in some circumstances, it is a rare occurrence.

To the contrary, because moving the storage implies moving the
data, which may be long and time consuming, some malloc packages go
to special efforts to avoid any moves, and thus modification of the
pointer to the block.

It's a debugging strategy. Typically you also pad the bytes with a pattern
like 0xC0 which is unlikely to be legitimate, stands out visually in the
debugger, and will produce a large negative index if used as an array
reference, and heance a segfault.
In production realloc() you probably won't do this to save time.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Richard]

Ian Collins <ia******@hotmail.comwrites:

CBFalconer wrote:

>Eric Sosman wrote:

>>CBFalconer wrote:
Chris Torek wrote:
Gene <ge**********@gmail.comwrote:
>"Malcolm McLean" <[e-mail]:
>>
>>... if memory is paged it might be possible to [implement
>>realloc() via] remap[ping] the page addresses without
>>physically copying data.
>This occurred to me, too. If you think about it, though, it
>won't work unless malloc() cooperates.
Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)
What __vmalloc and __pagealloc functions? No such thing in std C.
Typos: Chris actually meant _vmalloc() and _pagealloc().

I still don't find those names, with or without leading '_', in the
standard.

Isn't it obvious from the context what they do? It's hard to tell if
you are being dense or obtuse.

Both. It's called being "chuckish".

[Kenny McCormack]

In article <g9**********@registered.motzarella.org>,
Richard <rg****@gmail.comwrote:
....

>Isn't it obvious from the context what they do? It's hard to tell if
you are being dense or obtuse.

Both. It's called being "chuckish".

By the way, who is older: CBF or John McCain?

[Gordon Burditt]

>>While probably not what you're thinking of, I've seen a simple

>>realloc() implementation in a book that _always_ relocated the
block. The purpose was to help diagnose intermittent errors that
were caused by callers forgetting that realloc() _could_ relocate
the block because, in some circumstances, it is a rare occurrence.

To the contrary, because moving the storage implies moving the
data, which may be long and time consuming, some malloc packages go
to special efforts to avoid any moves, and thus modification of the
pointer to the block.

It's a debugging strategy. Typically you also pad the bytes with a pattern
like 0xC0 which is unlikely to be legitimate, stands out visually in the
debugger, and will produce a large negative index if used as an array
reference, and heance a segfault.

malloc(), realloc() and free() are not required to fill newly
allocated (in the case of realloc(), the expansion area if more
memory was requested) and freed memory with 0xdeadbeef, even on
32-bit systems. But they might anyway (especially in a debugging
mode). 0xdeadbeef (or, in the case of 64-bit systems, 0xdeadbeefdeadbeef)
was chosen to be (a) negative, (b) large, so it will stand out if
it's interpreted as an integer, (c) pessimally aligned and likely
to be an invalid pointer regardless of endianness, and (d) recognizable
in hex dumps. You hope that if the value is used, the program will
bomb spectacularly and quickly.

A debugging free() which garbage-fills freed memory can often detect
bugs in freeing linked lists (free the element, THEN pick up the
"next" pointer) for programs you thought were working fine most of
the time. A debugging realloc() which garbage-fills freed memory
can often detect spots where the memory moved but you referenced
the old memory anyway.

>In production realloc() you probably won't do this to save time.

True.